P1106 删数问题 - 洛谷
一、题目信息
1、题目链接：P1106 删数问题 - 洛谷
二、题目分析
1、分析：综合他人题解和自己思考归纳出本题的几个要点并应用到自己的解法中（要点只针对笔者自己的解法，不必须），浅记
- 考虑保留n-k位数的情况而非去除k位数的情况，原因即我们的目标是留下的数字组成的数的最大者，那就是考虑留下的数了
- 贪心：
- 从数串左到右选也即从最高位向最低位选，这样有两个好处：(1)从左到右顺序遍历，简单方便；(2)优先考虑高位的情况，因为高位对整个数大小的影响绝对大于低位。从而选每一位数时存在左边界，左边界左侧的数不能再被选择。
- 对于每一位，给它一个尽可能小的数，则从0开始选直到9，只有10种选择/情况。从而在确定结果的某一位的数是什么的时候，我们不从数串中找，而是在0~9这10个数中找，同时要满足一定要求（比如至少数串中得有这个数以及这个数在数串中的位置得合适等等），相比于从数串中找清晰而简单
- 结果的第一位数字应当在数串的前k+1位数字中，第二位数字应当在数串的前k+2位数字中，以此类推，从而选每一位数时存在右边界，只能选择数串中位置不超过右边界的数
2、思路：
- 遍历一遍数串，记录每个数的位置，则我们从0到9选数的时候就可以知道某个数在数串中的哪些位置有它的身影，如对于数串1283451391，1这个数出现在数串的第1、第7、第10个位置。
- 从最高位到最低位顺序选择确定，为每一位数选择尽可能小的数。
- 说不清楚，看代码吧...
三、代码
#include<unordered_map>
#include<queue>
#include<iostream>
using namespace std;int main(){string num_string;int k;cin>>num_string>>k;int retain=num_string.size()-k;unordered_map<int,queue<int>> num_to_loc;for(int i=0;i<num_string.size();i++){int now=num_string[i]-'0';num_to_loc[now].push(i+1);}if(retain==1&&num_to_loc[0].size()>0){cout<<0;return 0;}//数字的可选下标范围。下标从1开始int left=1,right=k+1; string result="";while(retain>0){for(int i=0;i<=9&&retain>0;i++){ //贪心，从小到大即从0到9依次选if(num_to_loc[i].empty()) continue;int loc=num_to_loc[i].front();while(loc<left){ //排除掉位置loc<left的数，这些数不会再被选到num_to_loc[i].pop();if(num_to_loc[i].empty()){loc=num_string.size()+1;}else{loc=num_to_loc[i].front();}}if(loc<=right&&retain>0){ //找到了一个数if(result!=""||i!=0){ //排除前导0result+='0'+i;}num_to_loc[i].pop();retain--;left=loc+1;right++; break; //跳出for循环，下一位继续从0开始找}}}cout<<result;return 0;
}