自动搬运

查看原文

来自洛谷，原作者为

	peppaking8 一起加油吧

搬运于2025-08-24 22:17:26，当前版本为作者最后更新于2020-02-18 15:54:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

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

进入正题。题目给了你一个字符串，你需要将一个字符出现的次数复制一遍，直到长度大于 $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
}

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