题解 | #完美串#

B-完美串_牛客挑战赛79

分析题意：不难理解，完美数组的定义，通俗来说，就是原数组s，m长度的子串的子串无重复。

思路：由完美数组的定义，我们知道m长度的子串中的每一个字符肯定是独一无二的，不然它的子串必然存在重复。 那么要怎么得到最长的m呢？不难看出，要想得出最长的m，我们就要把出现最多的字符尽可能地隔开，假设t为出现的最大次数，设k是有多少种出现次数为t的字符种类。

分析下图：，a代表m的组数，由图可以得出，， 由此，

代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Word{
	char c;
	int w;
};
struct cmp{
	bool operator()(const Word& a,const Word& b){
		if(a.w==b.w)return a.c>b.c;
		return a.w<b.w;
	}
};//自定义比较规则，让权值大的，且字母小的在前
const int N=200;
int Count[N];//记录每个字符出现次数
priority_queue<Word,vector<Word>,cmp> pq1;
priority_queue<Word,vector<Word>,cmp> pq2;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	string s;cin>>s;
	int n=s.size();
	int t=0,k=0;
	for(int i=0;i<n;i++)Count[(int)s[i]]++;
	for(int i=97;i<N;i++)t=max(t,Count[i]);
	for(int i=97;i<N;i++){
		if(Count[i]==t)k++;
	}
	
	for(int i=97;i<N;i++){
		if(!Count[i])continue;
		pq1.push({(char)i,Count[i]});
	}
	
	if(t==1){
		cout<<n<<'\n';
		cout<<s;
	}
	
	else{
		int m=(n-k)/(t-1);//由推导得
		for(int i=0;i<n;i++){
			//分阶段进行操作
			if(i%m==0){
				while(!pq2.empty()){
					Word tmp=pq2.top();pq2.pop();
					pq1.push(tmp);
				}
				pq1.swap(pq2);
			}
			Word tmp=pq2.top();pq2.pop();
			s[i]=tmp.c;
			tmp.w--;
			pq1.push(tmp);
		}
		
		cout<<m<<'\n';
		cout<<s;
	}
	return 0;
}