贪心算法（删数问题）-创新互联

数学原理：

从第一个数开始遍历，到找到单调递减的第一个数（即单调递增的最后一个数），则删除，若无单调递减子序列，则删掉最后一个非递减序列的数；每找到一个就又从头开始。即每做一次删数，就是一次贪心选择，删掉此数剩下的数为组成最小，经过证明，此结论正确。

创新互联服务项目包括清流网站建设、清流网站制作、清流网页制作以及清流网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，清流网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到清流省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

eg：

42135

单调递减的第一个数为第一个数为4，删掉得到2135

之后单调递减的第一个数为2，删掉得到135

不存在单调递减序列，则删除最后一个数5

需要注意的是：2001删除一个数后应该为1，而不是001，需要进行处理

#include 
#include​
using namespace std;
​
int shanshu(string &a, int k);
int main() {
    string st;
    int n, startIndex = 0;
    cin >>st >>n;
    n = shanshu(st, n);
    for (int i = 0; i< n; i++) {
        if (st[i] == '0') {
            startIndex++;
        }
    }
    for (int i = startIndex; i< n; i++) {
        cout<< st[i];
    }
​
    return 0;
}
int shanshu(string &a, int k) {
    int n = a.size(), j = 0;
    while (k >0) {
        for (int i = 0; i< n; i++) {
            if (a[i] >a[i + 1]) {
                for (int j = i; j< n; j++) {
                    a[j] = a[j + 1];
                }
                n--;
                break;  // 忘记退出循环了
            } else if (i == n - 1) {
                n--;
                break;
            }
        }
        k--;
    }
    return n;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

标题名称：贪心算法（删数问题）-创新互联
分享地址：http://bzwzjz.com/article/ceeesp.html