P1323 删数问题 【洛谷算法习题】

P1323 删数问题

网页链接

P1323 删数问题

题目描述

一个集合有如下元素：1 11是集合元素；若P PP是集合的元素，则2 × P + 1 2\times P+12×P+1，4 × P + 5 4\times P+54×P+5也是集合的元素。

取出此集合中最小的k kk个元素，按从小到大的顺序组合成一个多位数，现要求从中删除m mm个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。

注：不存在所有数被删除的情况。

输入格式

只有一行两个整数，分别代表k kk和m mm。

输出格式

输出为两行两个整数，第一行为删除前的数字，第二行为删除后的数字。

输入输出样例 #1

输入 #1

5 4

输出 #1

137915 95

说明/提示

数据规模与约定

• 对于30 % 30\%30%的数据，保证1 ≤ k , m ≤ 300 1\le k,m\le3001≤k,m≤300。
• 对于100 % 100\%100%的数据，保证1 ≤ k , m ≤ 3 × 10 4 1\le k,m\le3\times10^41≤k,m≤3×104。

解题思路

本题分为集合元素生成和贪心删数两大核心步骤。集合元素以 1 为起点，按规则递推生成，采用小根堆（优先队列）维护元素顺序，每次取出堆顶最小元素拼接成字符串，同时将新生成的两个元素入堆，直至取满 k 个元素。删数环节为经典贪心问题：遍历字符串，删除第一个小于后一位字符的字符，重复 m 次即可得到最大数字；若字符串全程非递增，则删除末尾 m 个字符。该方案逻辑简洁，时间复杂度高效适配k 、 m ≤ 3 × 10 4 k、m≤3×10^4k、m≤3×104的数据规模。

总结

核心逻辑：小根堆生成集合最小 k 个元素，贪心策略删除 m 个字符得到最大数。
关键操作：优先队列维护有序元素、遍历删除升序前置字符完成删数。
效率保障：堆操作保证元素有序，贪心删数线性遍历，无冗余计算，完美适配题目数据范围。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll k,m;priority_queue<ll,vector<ll>,greater<ll>>cre;string s;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>k>>m;cre.push(1);for(ll i=1;i<=k;i++){ll x=cre.top();s+=to_string(x);cre.pop();cre.push(2*x+1);cre.push(4*x+5);}cout<<s<<endl;ll cnt=0;for(;;){for(ll i=0;i<(ll)s.size()-1;i++){if(s[i]<s[i+1]){cnt++;s.erase(i,1);if(cnt>=m){cout<<s<<endl;exit(0);}break;}}}return0;}