CF1975H 题解
DaiRuiChen007
·
·
题解
Problem Link
题目大意
给定长度为 n 的字符串 s，重排 s 以最小化 s 的最大字典序子串。
数据范围：n\le 10^6。
思路分析
首先一个字符串的最大字典序子串一定是后缀，且由最大字符 z 开头。
同理末尾不为 $z$ 时把末尾放在最后一个 $z$ 的前面，答案变小。
因此可以调整使得开头结尾都是 $z$，原串就可以写成 $z+S_1+z+S_2+z+\dots+z+S_k+z$ 的形式。
假设 $S_1\sim S_k$ 已知，我们可以把所有 $z+S_i$ 看成单个字符，然后这个问题变成一个 $k$ 个字符的新问题。
因此我们只需要确定所有 $S_i$，排序可以递归解决
并且根据朴素贪心，如果当前的最大后缀从 $z+S_i$ 开始，那么把某个 $j<i$ 的 $S_j$ 里的字符放到 $S_i$ 末尾更优。
如果 $n-k<k$，那么显然每个 $|S_i|\le 1$，否则把 $|S_i|=2$ 的一个字符给 $|S_i|=0$ 的串显然更优。
那么每个 $S_i$ 都是一个字符，递归一次就会给每个 $S_i$ 前面加一个 $z$，进行 $\lfloor (n-k)/k\rfloor$ 轮，然后变成 $n-k\ge k$ 的情况。
对于这种情况，显然每个字符串的开头一定是字符集中最小的 $k$ 个元素，此时如果 $S_i$ 不是最大值，那么 $z+S_i$ 不可能成为最大后缀，那么我们只要在最大的 $S_i$ 后面继续放字符集中最小的元素，不断递归。
容易发现每次两次递归后 $n$ 减半，因此只会递归 $\mathcal O(\log n)$ 轮。
时间复杂度 $\mathcal O(n\log n)$。
**代码呈现**
```cpp
#include<bits/stdc++.h>
using namespace std;
string core(vector <string> S) {
if(S.empty()) return "";
int n=S.size(),x=1;
string z=S[n-1];
for(int i=n-2;i>=0&&S[i]==z;--i) ++x;
if(x==1) return z;
int y=n-x;
if(y>=x) {
int w=x-1,len=w;
vector <string> T(w,z);
for(int i=0;i<y;) {
int nw=len;
for(int p=w-len;p<w&&i<y;++p,++i) {
T[p]+=S[i];
if(p+1<w&&S[i]<S[i+1]) nw=w-p-1;
}
len=nw;
}
return core(T)+z;
}
vector <string> T;
int k=x/(y+1);
string kz="";
for(int i=0;i<k;++i) kz+=z;
for(int i=0;i<y;++i) T.push_back(kz+S[i]);
for(int i=0;i<x%(y+1);++i) T.push_back(z);
return core(T)+kz;
}
void solve() {
int n; string s;
cin>>n>>s;
vector <string> S;
for(auto c:s) S.push_back(string(1,c));
sort(S.begin(),S.end());
cout<<core(S)<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
int T; cin>>T;
while(T--) solve();
return 0;
}
```