删去k个数字后的最小值

问题描述：

给出一个整数，从该整数中去掉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;}

更多相关文章

随机推荐