题解 P6101 【[EER2]出言不逊】

· · 题解

思路：

我知道了，但你出言不逊是！！

进入正题。题目给了你一个字符串，你需要将一个字符出现的次数复制一遍，直到长度大于 L。求最小步数。

首先，第一次操作，最大可以到多少长度呢？这很显然，我们记录每个字符出现的次数，统计一个最大值即可。

第二次操作呢？由于我们第一次操作做了个数最多的一个字符，将其个数乘 2，所以这个字符出现的次数仍是最多的！故最优方案仍是操作这个字符。

所以整体方案就出来了，设字符 c 在原始字符串中出现的次数最多，那么就记录一个个数 cnt,每次判断如果当前长度 L' 加上 cnt 超过 L，那么就退出循环；否则，将 L' 加上 cnt，并将 cnt 乘上2即可。

这就是一个模拟，代码写起来比较流畅。

请注意：因为 L\le 2^{64}-1，所以要开 unsigned long long ！

代码：

#include<bits/stdc++.h>
#define int long long //写起来方便
using namespace std;
const int N=10005;
string s;
unsigned int l;
unsigned int cnt[N];
unsigned int mx=0,ans=0;
unsigned int max(unsigned int k1,unsigned int k2){
    if(k1>k2) return k1;
    else return k2;
}
signed main(){
//注意，因为我们定义了int为long long，所以int main()会被识别为long long main()，就不对了。
//所以说改为signed main()。
    cin>>s>>l;//输入
    unsigned int len=s.size();
    if(len>=l){//特判，如果已经可以出言不逊，输出0
        printf("0\n");
        exit(0);
    }
    for(unsigned int i=0;i<len;i++) cnt[s[i]]++,mx=max(mx,cnt[s[i]]);
    //直接char转int记录，只要开数组足够大
    while(1){
        if(l-len<=mx){
        //如果当前的len+mx>=l，就记录答案，推出循环
            ans++;
            break;
        }
        //否则，当前长度增加mx，mx乘2，计数器加1
        len+=mx;
        mx*=2;
        ans++;
    }
    cout<<ans<<endl;
    //输出计数器的值
    return 0; 
    //程序返回值0
}

写题解不容易，看完记得点个赞再走呀~