洛谷-P1106 删数问题（基础贪心）

题目描述

键盘输入一个高精度的正整数NN（不超过250250位） ，去掉其中任意kk个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的NN和kk，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

nn (高精度的正整数)

kk(需要删除的数字个数)

输出格式

最后剩下的最小数。

输入输出样例

输入 #1

175438 
4

输出 #1

13

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s; cin >> s;
    int k; cin >> k;

    int cnt = 0;
    while (cnt < k) {
        ++cnt;

        int n = s.size();
        bool haveDel = false;
        //删除逆序对的第一个数字
        for (int i = 0; i < n - 1; ++i) {
            if (s[i] - '0' > s[i + 1] - '0') {
                haveDel = true;
                s = (i > 0 ? s.substr(0, i) : "") + s.substr(i + 1);
                break;
            }
        }
        //如果序列升序，删除末尾的数字
        if (!haveDel) s = s.substr(0, n - 1);
    }
    //去除前导零
    int pos = 0, n = s.size();
    while (pos < n - 1) {
        if (s[pos] - '0' == 0) ++pos;
        else break;
    }
    cout << s.substr(pos) << endl;

    return 0;
}

每一次总是选择一个使剩下的数字最小的删去，那么显然删掉的数字应该在高位，那么就从高位往低位搜索。若数字递增，删掉末尾的数字；否则删掉第一个相邻降序数对的第一个数字。重复s次。注意最后输出结果的时候，要删除前导零。