E-小红的字符串重排

看的@Silencer76大佬题解（在吐槽区），用c++再写了一遍，写了非常详细的注释，面向像我一样的小白

（┭┮﹏┭┮）

具体思路请看代码

//		https://ac.nowcoder.com/acm/contest/92662/E
//		*	*	*	*
//		字符串重排

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int t,n;
void solve(){
	string s;
	cin>>s;
	n=s.size();
	int cnt[500];
	memset(cnt,0,sizeof(cnt));
	int mx=0;
	vector<pair<char, int>>v(n);
	vector<char> ans(n);
	for(int i=0;i<n;i++)
	{
		v[i].first=s[i],v[i].second=i;//v的key存字母，value存下标，而v的下标是0，1，2... n-1
		cnt[s[i]]++;//计数，记录每种字母的数量
		mx=max(mx,cnt[s[i]]);
	}
	if(mx>n/2)//最大的重复字母的数量不能大于s的长度的一半
	{
		cout<<-1<<endl;
		return ;
	}
	//按字母顺序排序，排完序后v按字典序的顺序排列，相同的字母挨在一起，但是字母对应的下标也会跟着变，因为这是键值对
	sort(v.begin(), v.end(), [](const pair<char,int>&v1, const pair<char,int>&v2){return v1.first<v2.first;});
	for(int i=0;i<n;i++)
	{
		//cout<<v[i].second<<" "<<v[(i+mx)%n].first<<endl;
		ans[v[i].second]=v[(i+mx)%n].first;//v[i].second为字母的下标，ans记录为该下标（v[i].second）对应的新的字母，就是v[(i+m)%n]位置的字母
	}
	cout<<string(ans.begin(), ans.end())<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

//例如：dbddbbe
//对v排完序之后是这样的：
// 0 ->  b-1	
// 1 ->  b-4
// 2 ->  b-5

// 3 ->  d-0
// 4 ->  d-2
// 5 ->  d-3
// 6 ->  e-6

//	   字母下标	  	     mx为最大的相同字母的数量
//ans[v[i].second()]   =   v[(i+mx)%n].first
//ans：下标 1 存 d-0 对应的的字母 d
//	   下标 4 存 d-2 对应的的字母 d
//	   下标 5 存 d-3 对应的的字母 d
//	   下标 0 存 e-6 对应的的字母 e
//		......