问题描述:

给出一个整数,从该整数中去掉k个数字,要求剩下的数字形成的新整数尽可能小,请用贪心法思想解决这个问题。

例如:

1.假设给出 1593212,删去3个数字,得到新整数 1212 (的话),此时最小;

2.假设给出 30200,删去1个数字,得到新整数 200 (的话),此时最小;

输入:要求输入正整数n,和去掉的数字个数k;

输出:打印输出,整数n被删除了k个数之后,最小的整数。

掉坑代码:
首先以为只要删去里面最大的数就OK了,结果后面发现这是不对的,举例说明:3549中删除9后是354,删除5后是349,所以不能这样想。

删去里面最大的数的代码(掉坑代码)

#include <iostream>using namespace std;int main(){int n, k, i = 0, s = 0, p;int num[10] = {0}, new_num[10] = {0};cin >> n >> k;while (n / 10 != 0)//把数分解单个的数字,并记录个数{num[i] = n % 10;n /= 10;i++;}num[i] = n;for (int j = 0; j < k; ++j)//需要去除几次最大数{int t = num[0], m = 0;for (int l = 0; l <= i; ++l)//寻找最大数{if (t < num[l]){m = l;t = num[l];}}for (int v = m; v <= i; ++v)//去除最大数{num[v] = num[v + 1];}i--;//数字个数-1}for (int x = i; x > -1; x--)//把数组转为正序{new_num[s] = num[x];s++;}for (p = 0; new_num[p] == 0; ++p)//去除0的开头{}for (int q = p; q < s; ++q)//输出{cout << new_num[q];}return 0;}

后面发现
只要原来的数从左到右进行比较,如果发现某一个数字比他右边的数字大,那么删除该数字后,必然会使该数位的值减小,因为右边比他小的数顶替它

#include <iostream>using namespace std;void remove(int num[],int i, int &s)//删除第i项{for (int j = i; j < s; j++){num[j] = num[j + 1];}s--;}void fun(int n, int k){int num[20] = {0}, s = 0, v = 0;for (s = 0; n / 10 != 0; ++s)//把数分解单个的数字,并记录个数{num[s] = n % 10;n /= 10;}num[s] = n;for (int i = 0; i <= s / 2; ++i)//把数组转化为正序{swap(num[i], num[s - i]);}for (int t = 0; t < k; t++){num[s + 1] = num[s];for (int i = 0; i < s; i++){if (num[0] > num[1])//当第一个数小于第二个数时{remove(num,i,s);break;}else if ((num[i-1] < num[i]) && (num[i] > num[i + 1]))//若大于前一项小于后一项{remove(num,i,s);break;}}}for (v = 0; num[v] == 0; v++)//除去0开头{}for (; v <= s; ++v){cout << num[v];}}int main(){int n, k;cin >> n >> k;fun(n, k);return 0;}