当前位置：首页 > 洛谷 > 洛谷P1323题解：优先队列与单调栈解决删数问题

洛谷P1323题解：优先队列与单调栈解决删数问题

18小时前

一、题目解读

洛谷P1323题要求生成前k个最小的元素，并通过删除m个数字使剩余序列单调递增。题目需结合生成算法与优化删除策略，考验对数据结构与贪心思想的运用。

二、解题思路

1. 生成最小k数：利用优先队列（最小堆）维护当前最小元素。每次取出队首元素，生成其衍生元素（2x+1和4x+5），避免重复后加入队列，直至得到k个元素。

2. 删除m数优化：将生成的数字拼接为字符串，采用单调栈策略。遍历字符时，若栈末尾数字小于当前数字且可删除次数剩余，则弹出栈顶直至满足条件，最终保留单调递增子序列。

三、解题步骤

1. 输入k和m，初始化优先队列pq（最小堆）并加入初始元素1。

2. 循环k次：

取出队首元素，若与上一元素重复则跳过。

加入队列的新元素为2x+1和4x+5，确保队列始终维护最小元素。

3. 将生成的k个元素拼接为字符串numStr。

4. 遍历numStr，利用单调栈删除：

若当前字符大于栈顶且可删除次数>0，弹出栈顶直至不满足条件。

将当前字符入栈，最终栈中序列即为删除m个数字后的最大单调递增子串。

5. 若剩余删除次数未用完，从末尾截断字符串。

6. 输出原始序列和优化后的结果。

四、代码与注释

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int k, m;
    cin >> k >> m; // 输入k和m
    
    // 优先队列(最小堆)生成k个最小元素
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<int> elements;
    pq.push(1); // 初始元素1
    
    while(elements.size() < k) {
        int current = pq.top(); // 取出最小元素
        pq.pop();
        // 避免重复元素
        if (!elements.empty() && current == elements.back()) {
            continue;
        }
        elements.push_back(current); // 加入有效元素
        // 生成新元素加入队列
        pq.push(2 * current + 1);
        pq.push(4 * current + 5);
    }
    
    // 拼接数字为字符串
    string numStr;
    for (int num : elements) {
        numStr += to_string(num);
    }
    cout << numStr << endl; // 输出原始序列
    
    // 单调栈删除m个数字优化
    string result;
    int remove = m;
    for (char digit : numStr) {
        // 贪心删除：若当前数字比栈顶大且可删除
        while (remove > 0 &&!result.empty() && digit > result.back()) {
            result.pop_back(); // 弹出栈顶
            remove--;
        }
        result.push_back(digit); // 加入当前数字
    }
    // 剩余删除次数从末尾截断
    if (remove > 0) {
        result = result.substr(0, result.size() - remove);
    }
    cout << result << endl; // 输出优化结果
    return 0;
}