/*日期:2011-10-20
作者:xiaosi
题目: 删数问题问题(贪心)
*/
#include<iostream>
#include<cstdio>
#include<stdlib.h>
using namespace std;
struct Num
{
char num;
int index;
}N[201];
int cmp(const void *a,const void *b)
{
struct Num *c = (Num *)a;
struct Num *d = (Num *)b;
return c->num - d->num;
}
int cmp1(const void *a,const void *b)
{
struct Num *c = (Num *)a;
struct Num *d = (Num *)b;
return c->index - d->index;
}
int main()
{
int i=0;
while(scanf("%c",&N[i].num)!=EOF)
{
int k,l;
N[i].index=0;
while(N[i].num!='\n')
{
i++;
scanf("%c",&N[i].num);
N[i].index=i;
}
l=i;
scanf("%d",&k);
qsort(N,l,sizeof(N[0]),cmp);
qsort(N,l-k,sizeof(N[0]),cmp1);
for(i=0;i<l-k;i++)
{
printf("%c",N[i].num);
}
printf("\n");
i=0;
getchar();
}
return 0;
}
分享到:
相关推荐
本主题将深入探讨“删数问题”的贪心算法C++实现。 ### 1. 贪心算法简介 贪心算法并不考虑整体最优解,而是每一步都追求局部最优解,假设这些局部最优解组合起来能导致全局最优解。贪心算法通常适用于问题的最优解...
### C++贪心算法解决删数问题 #### 题目背景与要求 该题目属于典型的算法类问题,主要考察的是贪心算法的应用。题目要求从一个给定的正整数`a`中删除`k`个数字(`k ≤ n`),使得剩下的数字按照原来的顺序排列后...
在这个名为“用贪心算法处理删数问题”的主题中,博主可能探讨了如何使用贪心算法来解决一个特定的数字处理或数组操作问题。 贪心算法的特点在于它的局部最优解能导向全局最优解。然而,并非所有问题都能通过贪心...
- **测试数据的使用**:书中提供的测试数据用于检验所写的贪心算法程序是否正确,并且能够处理各种边界情况和复杂度较高的输入。 在学习这一章时,读者应该通过分析问题,确定贪心选择性质,并编写程序来实现这个...
尽管贪心算法不能保证对所有问题都能找到全局最优解,但在像删数问题这样的具有最优子结构和贪心选择性质的问题上,它可以给出正确答案。 对于时间复杂度,由于算法主要涉及一次遍历字符串的操作,时间复杂度可以视...
删数问题 算法分析 ACM 贪心算法 Description 对于一个有 n 个数字的正整数 a, 去掉其中任意 k (≤ n) 个数字后, 剩下的数字按原次序排列组成一个新的正整数. 本题对于给定的正整数 a, 请计算删去 k 个数字后...
此程序能解决删除问题,效率高,结果正确。对于理解贪心算法有很大帮助。
在18位整数...16485679数中删除4个数字的贪心操作步骤。 1 6 4 8 5 6 7 9 出现1删除6 6 4 8 5 6 7 9 出现4删除4 6 8 5 6 7 9 出现6删除6 8 5 6 7 9 出现5删除5 8 6 7 9 删除4个数字后,最大的数是8679
删数问题 Description 给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个 新的正整数。对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «...
- **输入**:多组测试数据(不超过50组),每组包含两个整数 a 和 k,其中 a 是一个 n 位的正整数(1 ),k 表示需要删除的数字个数(0 )。输入以0结束。 - **输出**:对于每组测试数据,输出在删除 k 个数字后得到...
图的着色问题是数据结构领域中一个经典的图论问题,旨在找到图中最少的着色数,并输出每个颜色下的顶点。该问题可以使用贪心算法解决。 贪心算法是一种常用的近似算法,用于解决NP-hard问题。它的思想是,每次选择...
这个问题是经典的算法问题,涉及到数组操作、排序以及贪心策略。题目要求我们设计一个算法,从给定的n位正整数a中删除k个数字,使得剩余数字组成的数尽可能小。这里的关键在于如何选择要删除的数字。 首先,我们...
### 贪心算法在背包问题中的应用及C语言实现 #### 一、贪心算法简介 贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过一系列的局部最优选择来达到全局最优解的目的。它适用于某些特定的问题类型,在...
通过对源代码的分析和实验数据的测试,我们可以深入理解贪心法的工作原理,并了解其在解决复杂优化问题时的优势和局限性。这对于我们理解和应用贪心算法,以及进一步研究更高级的求解策略,如动态规划或遗传算法,都...
贪心算法是解决这类问题的一种策略,它通过每一步选择局部最优解来期望得到全局最优解。在这个场景中,我们将探讨如何使用Java编程语言,结合贪心算法,来解决背包问题。 首先,我们要理解贪心算法的基本思想。贪心...
贪心算法解决单源最短路径问题的基本思想是分步求出最短路径,每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过贪婪准则选取,即选择路径最短的目的顶点。设置顶点集合S,并不断作贪心选择来...
在实现贪心算法时,Python提供了方便的数据结构,如列表、字典和集合,这些都可以用来有效地表示和操作问题的各个方面。例如,我们可以使用列表来存储待合并的文件,用字典来记录每个文件的大小或属性,以及合并后的...
### 贪心算法在活动安排问题中的应用 #### 一、引言 在计算机科学领域,贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过这种方式找到全局最优解。活动安排问题(Activity Selection Problem)是贪心...
总结来说,这个压缩包包含了一个使用贪心算法求解旅行商问题的C语言程序,以及相关的项目文件和输入数据。尽管贪心算法无法保证找到TSP的全局最优解,但对于小型问题实例,它仍然能提供一种接近最优的解决方案。对于...
在计算机科学与编程的实践中,活动安排问题、汽车加油问题和删数问题是三个具有代表性的经典问题,它们分别涵盖了贪心算法、动态规划以及结合数学策略的算法设计思想。这三个问题不仅在学术研究中占有一席之地,而且...