问题描述:设计一个贪心算法,使得对于给定的n位正整数,在删除其中任意k<=n位数字后,剩余的数字按原来的次序排列组成的新的正整数最小 输入:第一行是一个正整数A,第二行是正整数k 输出:剩余数字组成的最小数,使用C语言并给出完整代码
时间: 2024-01-22 18:17:18 浏览: 89
用贪心算法处理删数问题
以下是使用C语言实现的贪心算法,可以解决这个问题:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char num[20];
int k;
scanf("%s%d", num, &k);
int len = strlen(num);
int resLen = len - k; // 剩余数字的长度
char res[resLen]; // 存储剩余数字
int top = 0; // 栈顶指针
for (int i = 0; i < len; i++) {
// 如果当前数字比栈顶数字小,弹出栈顶数字
while (top > 0 && num[i] < res[top - 1] && k > 0) {
top--;
k--;
}
// 将当前数字入栈
if (top < resLen) {
res[top++] = num[i];
} else {
k--; // 如果剩余数字已满,删掉当前数字
}
}
printf("%s", res);
return 0;
}
```
该算法的思路是,从左到右遍历原数的每一位数字,将其依次加入一个栈中。如果当前数字比栈顶数字小,就弹出栈顶数字,直到当前数字比栈顶数字大或栈为空或需要删除的数字数目已达到上限(即已删除了k个数字)。如果栈未满,则将当前数字入栈;否则,也需要删除当前数字。最后,栈中剩余的数字即为剩余数字组成的最小数。
需要注意的是,由于输入的数字可能很大,所以需要使用字符数组存储,而不能使用int类型。
阅读全文