算法竞赛c++.新人每日一练.贪心算法（P1106删数问题 洛谷）

该题仍然是贪心思维，但是不能只思考删去最大的数字。如反例13245，做一次删数操作。删去最大的数得到1324，但删去3得到的数是1245.这是因为虽然删去的5是虽然是最大的数，但是3还在数字的高位上（就是百位）。所以要分情况讨论一下，如果是递增的数字12345，那删去最大的数字5是没问题的。但如果是有递减的部分如13245，那么应该删去先删去3这样的数字，使得数字重新成为递增的1245。

#include<iostream> #include<string> using namespace std; char a[1001]; int k, len; int main() {//123465 cin >> a >> k; len = strlen(a); for (int i = 1; i <= k; i++)//该循环 循环 k次做删数 { for (int j = 0; j < len; j++) //该循环是单次的删数 { //if 检测是否有递增的部分，发现有进行删数处理 if (a[j] > a[j + 1]) { for (int l = j; l < len; l++) a[l] = a[l + 1]; len--; break; } } } int t = 0; //此处进行删除前面多余的0操作，如100009，删去1 应该为0 while (t < len && a[t] == '0') t++; if (t == len)cout << "0"; else for (int i = t; i < len; i++) cout << a[i]; return 0; }

很多读者会疑惑： 如果数字是完全递增的 12345，代码里没有专门写“删除最后一位”，为什么还能正确运行？

秘密在于： 我们的数组 a 是全局变量，未手动赋值的位置会自动初始化为 0。 当遍历到 j = len-1（即数字最后一位 5）时： a[j] = '5' ，a[j+1] = 自动赋的 '0' 满足 a[j] > a[j+1]，因此会删除最后一位 5，完美处理了完全递增的情况。

特别注意：

如果数字结尾是 0，例如 123450， 遍历到 5 和 0 时会触发递减检查，删除 5，得到 12340，而不是保留 5。 这也符合贪心规则。

本文参考书籍：《趣味算法：用C++实现》作者：喻蓉蓉 刘弘洋