洛谷P1323题：从集合生成到数字删除解决删数问题

2天前洛谷题解58

这道题目实际上包含两个主要部分：1) 按照特定规则生成集合中的前k个最小元素；2) 将这些数字拼接后删除m个数字，使剩余数字最大。我们需要分别解决这两个子问题。

一、集合元素的生成

集合生成规则告诉我们：

1是集合中的元素
如果P在集合中，那么2×P+1和4×P+5也在集合中

为了高效生成前k个最小元素，我们使用了优先队列（最小堆）数据结构。这种方法确保了每次都能取出当前最小的元素进行处理。

实现细节

初始化优先队列，放入起始元素1
循环直到收集到k个元素：

取出堆顶最小元素
检查是否重复（避免同一元素多次处理）
将该元素加入结果集
生成两个新元素(2×P+1和4×P+5)放入优先队列

这种方法的时间复杂度是O(k log k)，因为每个元素最多被处理一次，每次堆操作是O(log k)。

二、数字删除策略

将生成的k个数字拼接成一个大数后，我们需要删除m个数字使剩余数字最大。这类似于经典的"删除k位数字使剩余数字最大"问题。

我们采用了单调栈的方法来解决这个问题：

算法思路

初始化一个空字符串作为结果
遍历原数字字符串的每个数字：

当还能删除数字(m>0)，且当前数字大于结果字符串的最后一个数字时，删除最后一个数字(m减少)
将当前数字加入结果字符串

如果遍历完后还有剩余的删除次数(m>0)，从结果字符串末尾删除相应数量的数字

这种方法确保了我们总是删除那些"阻碍"数字变大的数字，时间复杂度是O(n)，其中n是数字字符串的长度。

三、完整代码

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

using namespace std;

int main() {
    int k, m;
    cin >> k >> m;
    
    // 使用优先队列(最小堆)来生成集合中最小的k个元素
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<int> elements;
    
    pq.push(1);  // 初始元素1
    
    // 生成前k个元素
    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;
}