Input
输入第1行为一个整数L
后面L行的每一行包括一个长度为N的高精度正整数和需要去掉的数的个数k。(1 <= N <= 1000 ， 1 <= k < N)
Output
输出每一行表示每个高精度正整数去掉相应的k个数字后构成的新的最大正整数。
Sample Input
Original Transformed
2
12345 1
54321 2
Sample Output
Original Transformed
2345
543
C语言有没有比较好的解决方法或者算法思路，自己编的程序总是出现一些小问题
分享
哪个OJ题目吧？
按照我的理解，这题不能排序，要保持原先的顺序，扩展一下几种样例情况以及我所给出的最大数：
123123 3 输出：323
1000 2 输出：10
322123 1 输出：32223
12345 3 输出：45
这题的要求是去掉k个数之后变得尽量大，那么也就是说，要让高位的数尽量大，也就是说，使得数字从高位开始尽量呈现递减的状态（前一位数要比后一位数大或者相等），而且我们在求值的时候是可以利用递推性的，比如k=2的结果可以在k=1的时候的结果上来取，也就是说k的结果可以在k-1的基础上进行获取。
我们以 123123 3 这种情况作为例子分析：
由于k=3，所以要去掉3个数，那么我们先求去掉2个数和去掉1个数的情况。
去掉1个数，也就是输入为123123 1 的时候：我们看123123的第一位和第二位分别是1和2，显然第一位要比第二位小，不符合递减状态，所以我们删掉第一位，那么就变成了 23123
去掉2个数，也就是输入为123123 2 的时候：在去掉1个数的结果23123的基础上，我们需要再去掉一个数。我们看到第一位第二位分别是2和3，显然不符合递减状态，所以删掉第1位的2，么那变成3123
去掉3个数：在去掉2个数的结果3123的基础上，我们看到第一位第二位分别是3和1，符合递减状态，所以我们需要看第二位和第三位，第二位是1第三位是2，显然不符合递减状态，所以删掉第二位，那么得到的是323。
所以，我们可以这样做：
对于每个输入样例，我们需要做k次循环，每次循环所做的事情是从最高位开始遍历，找出不符合递减状态的第一个数，将其删掉。这样在k次循环之后我们就能获取到最大的数。
整理之后的代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//从start位置开始到end结束，整体后移一位，将end的位置覆盖掉
void moveOneStep(char * bigNum,int start,int end) {
for (int i=end; i>start; i--) {
bigNum[i]=bigNum[i-1];
}
}
int main()
{
int L;
//输入L
scanf("%d",&L);
while (L--) {
//做acm的话数组稍微开大一点点，因为有些题目会很坑，可能会出违背题目要求的内容
char bigNum[1005];
int k;
//输入大数
scanf("%s",bigNum);
//长度
long long length = strlen(bigNum);
//获取k
scanf("%d",&k);
if (k >= length) {
printf("不合法的输入\n");
continue;
}
//核心代码
for (int i=0; i<k; i++) {
for (int j=i; j<length; j++) {
if (bigNum[j] < bigNum[j+1] || j == length - 1 ) {
//使用了位移覆盖的方式来删除
moveOneStep(bigNum,i,j);
break;
}
}
}
//将字符串前移k位，也就是将原先后移的都移回来
for (int i=0; i<length - k; i++) {
bigNum[i] = bigNum[i+k];
}
//限定字符串长度为 length - k
bigNum[length - k ] = '\0';
printf("%s\n",bigNum);
}
return 0;
}
这是用数组来实现的方式,每删除一个都需要位移一次，复杂度近乎为0(n2)，其实可以用一个当前位置指针来进行优化，不过复杂度不会有太大变化。
另外也可以用链表来实现，如果用链表来实现的话，删除将会方便很多，实现的思想是差不多的，不过如果借助一个当前位置指针的话复杂度可以下降到0(n)。
分享
