使用C语言 键盘输入一个高精度的正整数n,去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。对给定的n和s,寻找一种方案使得剩下的数字组成的新数最小。(采用贪心算法)
时间: 2023-08-20 15:21:11 浏览: 102
好的,下面给出利用贪心算法解决这个问题的思路和代码实现。
贪心算法的基本思路是每次选择局部最优解,并希望最终得到的全局解也是最优的。对于这个问题,我们可以从高位开始,每次删除尽可能小的数字。
具体来说,我们可以用一个栈来存储当前还未删除的数字,从高位到低位遍历原始数字n。对于当前的数字,如果栈不为空且栈顶元素比当前数字大且还未删除的数字个数小于s,则弹出栈顶元素,直到栈为空或栈顶元素比当前数字小或还未删除的数字个数达到s为止。然后将当前数字压入栈中。遍历结束后,如果还未删除的数字个数小于s,则从栈顶开始删除数字,直到还未删除的数字个数达到s为止。
下面是利用贪心算法求解的代码实现:
```
#include <stdio.h>
#include <string.h>
#define MAXN 100000
char n[MAXN + 1];
int stack[MAXN], top = -1;
int main() {
int s;
scanf("%s%d", n, &s);
int len = strlen(n);
for (int i = 0; i < len; i++) {
int num = n[i] - '0';
while (top >= 0 && stack[top] > num && top + len - i > len - s) {
top--;
}
if (top < len - s - 1) {
stack[++top] = num;
}
}
int i = 0;
while (i <= top && stack[i] == 0) i++;
if (i > top) printf("0");
else {
while (i <= top) {
printf("%d", stack[i++]);
}
}
return 0;
}
```
希望这个例子能够帮助到你!
阅读全文