题解 P1323 【删数问题】

· · 题解

其实，这是由两条题目凑在一起，拼接而成的一条题目。

而这两题，在JS夏令营冬令营，NT国庆冲刺营中都有出现。

分别是丑数（队列部分的题目，但似乎题面各有不同，这是其中的一个版本，是符合真正数学定义“丑数”的）和删数问题（没错，名字一模一样）（贪心部分题目）后一题可参考我写的题解。

把本题拆分成两部分。首先，把这些元素全都找出来并拼接在一起，然后，逐渐删去。

  1. 找元素

    由于题中说是“最小的k个元素”“从小到大”，所以是依次添加元素，而每次都 O(n) 去找目前最小的元素显然不现实，手写二分由太过麻烦，所以考虑STL中的优先队列->priority_queue。

    priority_queue 默认是大根堆（即大的元素在前），所以我们需要修改参数，变为小根堆，这样就可以每次 O(logn) 找出当前最小的元素，取出并添加它的两个附属元素。

priority_queue<int,vector<int>,greater<int> > q;
//int 是数据类型，vector 是存储方式（据说也可以用其他的），greater/less 控制大根堆，小根堆

  1. 拼接 在这里给大家介绍一种黑科技：to_string (很不幸的是，它隶属于 c++11，所以竞赛中不能使用，但在平时做题时使用是没有问题的)

    to_string 可以将数字转化为所对应的字符串（特殊、奇怪的字符就不要出现了）不仅仅是 int ！double,float,long long,long double 等都是支持的。 所以我们在取出目前最小元素后，可以使用 to_string 将其转化为字符串，然后进行字符串的累加。（若不用 to_string，也可以通过取模的方式，将数字依次取出，然后转化成 char 进行拼接）

  2. 寻找要删除的数字 可以发现：本质上就是维护一个不下降序列 并不会数学证明，故通过举例说明： 29523->9523->953->95->9 其实就是与它同名的删数问题的翻版，本题要求剩下的数最大，它要求剩下的数最小，规律是反过来的（大于号、小于号的区别）

  3. 如何删除 使用 string 中的 erase 函数。写法： 

    str.erase(起始位置,删除的长度)

    5.循环的写法 由于不知道如何删除，外面应该是一个 while(1) 或 for( ; ; )，内部枚举字符串中的每位。删去一个，记录一次，达到总次数便立即退出，可使用 exit(0) 直接退出整个程序（也可以用标记的形式，达到总次数后更改标记，外部循环每次都判断标记）

    #include<bits/stdc++.h>
using namespace std;
int k,m;
priority_queue<int,vector<int>,greater<int> > cre;
string s;
int main(){
cin>>k>>m;
cre.push(1);
for(int i=1;i<=k;++i){
    int x=cre.top();
    s+=to_string(x);
    cre.pop();
    cre.push(2*x+1);
    cre.push(4*x+5);
}
cout<<s<<endl;
int cnt=0;
for(;;){
    for(int i=0;i<s.size()-1;++i){
        if(s[i]<s[i+1]){
        ++cnt;s.erase(i,1);
        if(cnt>=m){cout<<s<<endl;exit(0);}
        break;
        }
    }
}
return 0;
}