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

该题仍然是贪心思维但是不能只思考删去最大的数字。如反例13245做一次删数操作。删去最大的数得到1324但删去3得到的数是1245.这是因为虽然删去的5是虽然是最大的数但是3还在数字的高位上就是百位。所以要分情况讨论一下如果是递增的数字12345那删去最大的数字5是没问题的。但如果是有递减的部分如13245那么应该删去先删去3这样的数字使得数字重新成为递增的1245。#includeiostream #includestring 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[j1] 自动赋的 0 满足 a[j] a[j1]因此会删除最后一位 5完美处理了完全递增的情况。特别注意如果数字结尾是 0例如 123450 遍历到 5 和 0 时会触发递减检查删除 5得到 12340而不是保留 5。 这也符合贪心规则。本文参考书籍《趣味算法用C实现》作者喻蓉蓉 刘弘洋