题解 P3718 【[AHOI2017初中组]alter】

· · 题解

虽然没有AC，但是我觉得贴出来让大家看看；简单贪心，使用优先队列，先把连续段落投入队列，然后每次取队列里最大的元素/2再加入队列，这样做能拿55

#include <iostream>//头文件最好都写上
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n,k,cnt=1,f;//f待会儿说
char las;//记录上一个元素
string s;//读入连续字符不用string要炸
priority_queue<int> li;//优先队列
int main(){
    cin>>n>>k;
    cin>>s,las=s[0];//las=s的第一个元素
    for(int i=1;i<s.size();i++){
        if(s[i]==las) cnt++;
        else if(s[i]!=las){//如果与前一段落元素不同就初始化并且投入段落
            if(i==s.size()-1) f=1;//这里的意思是防止最后一个元素被反复投入，见下
            li.push(cnt);
            cnt=1,las=s[i];
        }
    }
    if(!f) li.push(cnt);//见上
    for(int i=1;i<=k;i++){//标题里很清楚，当然要记得把元素取出后要删除
        int x=li.top();
        li.pop();
        x/=2;
        li.push(x);
    }
    cout<<li.top();//输出最大即可
    return 0;
}