P1323 删数问题网页链接P1323 删数问题题目描述一个集合有如下元素1 11是集合元素若P PP是集合的元素则2 × P 1 2\times P12×P14 × P 5 4\times P54×P5也是集合的元素。取出此集合中最小的k kk个元素按从小到大的顺序组合成一个多位数现要求从中删除m mm个数位上的数字使得剩下的数字最大编程输出删除前和删除后的多位数字。注不存在所有数被删除的情况。输入格式只有一行两个整数分别代表k kk和m mm。输出格式输出为两行两个整数第一行为删除前的数字第二行为删除后的数字。输入输出样例 #1输入 #15 4输出 #1137915 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 个字符得到最大数。关键操作优先队列维护有序元素、遍历删除升序前置字符完成删数。效率保障堆操作保证元素有序贪心删数线性遍历无冗余计算完美适配题目数据范围。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll k,m;priority_queuell,vectorll,greaterllcre;string s;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinkm;cre.push(1);for(ll i1;ik;i){ll xcre.top();sto_string(x);cre.pop();cre.push(2*x1);cre.push(4*x5);}coutsendl;ll cnt0;for(;;){for(ll i0;i(ll)s.size()-1;i){if(s[i]s[i1]){cnt;s.erase(i,1);if(cntm){coutsendl;exit(0);}break;}}}return0;}
