洛谷题单指南-贪心-P1106 删数问题

原题链接：https://www.luogu.com.cn/problem/P1106

题意解读：如何删数，让剩下的数最小，贪心选择问题。

解题思路：

先看样例：

175438 
4

第1次遍历：删掉7，剩下15438

第2次遍历：删掉5，剩下1438

第3次遍历：删掉4，剩下138

第4次遍历：删掉8，剩下13，即为结果

所以，贪心策略如下：

1、遍历每一个数，如果前一个数比后一个数大，则删掉前一个数

2、以上过程重复k次，即删除k个数

3、特别的，如果是最后一个数，要和0比较，如果比0大则删掉最后一个数

需要注意两点：

1、如果数全部被删除，答案是0，需要特殊处理

2、删除后，可能出现前导0，输出时需要去除前导0

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 255;

string s;
int a[N], cnt, k;

int main()
{
    cin >> s >> k;
    for(int i = 0; i < s.size(); i++) a[i + 1] = s[i] - '0';
    cnt = s.length();

    while(k--) //删k次
    {
        for(int i = 1; i <= cnt; i++) //从头到尾遍历
        {
            if(a[i] > a[i + 1]) //前面数比后面的数大，则删掉前面的数，注意最后一个数要和0比较
            {
                for(int j = i; j <= cnt; j++) //删掉a[i]
                {
                    a[j] = a[j+1];
                }
                cnt--; //数的数量减少1个
                break;
            }
        }
    }

    if(cnt == 0) cout << 0; //都被删了，输出0
    else
    {
        int i = 1;
        while(!a[i] && i < cnt) i++; //去除前导0
        while(i <= cnt) cout << a[i++];
    }
     

    return 0;
}