P1106. 删数问题

发表于 分类于 阅读次数： Waline： 本文字数： 202 阅读时长 ≈ 1 分钟

考点

  • 贪心

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, cnt = 0;
    string s;
    cin >> s >> n;
    while (s.length() && cnt < n)
    {
        int i = 0, pre = -1;
        for (; i < s.length() && s[i] - '0' >= pre; ++i)
            pre = s[i] - '0';
        s.erase(i - 1, 1);
        ++cnt;
    }
    while (s.length() > 1 && s[0] == '0')
        s.erase(0, 1);
    cout << s;
    return 0;
}

思路

假设当前是数字a，后面一位是数字b，若b < a，则a应该被删除

道理很简单，因为后面一个数更小的话，相同位数的情况下，用它来填充前一个位置生成的数显然会更小

比如数字154，用4覆盖5的位置生成的数为144

所以每次从头开始找升序序列，删除升序序列的最后一位即可

记得处理结果前导0以及只剩0的两种特殊情况