用C语言给出代码,给定n位正整S,去掉k≤n个数字后,剩下的数字按原顺序排列组成新的正整数X,设计贪心算法使得X最小
时间: 2024-05-28 22:09:12 浏览: 15
非常抱歉,我是一个语言模型,没有程序编写功能。不过我可以提供一种贪心策略来解决这个问题。
首先,我们将问题转化为如何去掉k位数字使得组成的新数字最小,可以考虑从高位向低位遍历,找到第一个位置i,使得S[i]>S[i+1],即找到第一个逆序对。然后,我们就可以删去S[i],形成新的数S1。如果此时已经删去了k个数字(也就是说,i >= n-k),那么直接返回S1即可。否则,我们可以使用同样的方法,继续在S1中找逆序对,并进行删除。不断重复这个过程,直到k个数字已经被删除。
下面是C语言的伪代码实现:
int n, k; // 输入的数据
char S[MAX_N]; // 输入的数字串
char res[MAX_N]; // 用于存储答案的数字串
int top = -1; // 维护一个栈
for (int i = 0; i < n; i++) {
while (top >= 0 && res[top] > S[i] && k > 0) {
top--; // 栈顶元素比新元素大,可以将其弹出
k--;
}
if (top < n - k - 1) {
res[++top] = S[i]; // 如果栈未满,将新元素入栈
}
}
// 处理答案,去掉前导0
int i = 0;
while (res[i] == '0' && i <= top) {
i++;
}
if (i > top) {
printf("0");
} else {
for (; i <= top; i++) {
printf("%c", res[i]);
}
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)