删数问题洛谷p1323

DLSQS-lkjh / 2023-08-14 / 原文

决定做一系列贪心，贪心真的，最早学的算法，到现在还有时候不太敢贪，还贪不来，一直挺逃避贪心问题的。。

删除前的数字可以先用优先队列对所有数字进行预处理，数据范围是3e4，也不是很大，直接全部处理了吧。

const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, MAX = 3e4 + 10;
int a[N];
priority_queue<int, vector<int>, greater<int>> q;
void start() {
    int cnt = 0;
    q.push(1);
    while (cnt <= MAX) {
        a[++cnt] = q.top();
        q.pop();
        q.push(2 * a[cnt] + 1);
        q.push(4 * a[cnt] + 5);
    }
}

预处理完后输出所需要的个数k个，再把这一串处理成字符串，这里用到了to_string()，可以直接把数字转换成字符串。

    start();//预处理
    int k, m;
    cin >> k >> m;
    string s;
    for (int i = 1; i <= k; i++) {
        string t = to_string(a[i]);
        s = s + t;
    }
    cout << s << endl;

然后就是删数问题了，就是求不上升子序列咯。

当遇到s[i]<s[i+1]时，就把第i个删除掉，计数器+1，为了避免后面的数依旧大于前面这个数，所以每次发现s[i]<s[i+1]后，如果所删除的个数cnt小于m的话，则跳出循环重新开始扫，以保证第一个数是当前情况下最大的（真的贪不出来），代码如下：

    while (1) {//因为不知道什么时候删除个数能等于m，所以就一直循环咯
        for (int i = 0; i < s.size() - 1; i++) {
            if (s[i] < s[i + 1]) {
                s.erase(i, 1);
                cnt++;
                if (cnt == m) {
                    flag = 1;
                    cout << s << endl;
                }
                break;
            }
        }
        if (flag)break;
    }