AT_abc416_g 题解

· · 题解

也许是双倍经验？哇，居然是“AT 原题在 AT”！

题目就是说，给你 n 个字符串 s_i。现在你可以其中选择 k 个字符串（可以重复选择）并将它们按顺序一一连起来，问最终得到的字符串中字典序最小的那个是多少，输出它。

乍一看，诶，是不是一个排序的事儿？G 这么简单？高高兴兴敲完代码，呃完蛋，最后一个样例过不了！

所以啦，当然没有这么简单！

首先我们的这 n 个字符串肯定要排序。但是怎么排序呢？当然不能用最普通的判断法！

让我们使出终极大招——如果要判断 s < t（这里的 < 指的是新型判断法），必须满足 s+t < t+s（这里的 < 指的是正常的字符串字典序判断法）！但如果 s+t = t+s 呢？那么直接按正常的字符串字典序判断法就行！

我们用这玩意儿排序！写成 cmp 比较函数。

接下来呢？考虑 k 为无穷大的情况，那么肯定是对排完序过后的 s_1 一直不断重复！

但是 k 实际上并不是无穷大啊。怎么办？

也很简单，那我们就查看后缀需要被替换成什么呗！

具体来说就是，当前我们维护出一个后缀 ans（一开始是空串），然后先令一个 tmp = s_1 + ans。接下来我们上擂台，让 s_2 \sim s_n 一一试试看，能不能超过 tmp。当然，这里用的都是正常的字典序比较法。一直延续这个后缀即可。

什么时候结束？这不是显然意见的嘛！当然是等到 s_1 稳居擂台，没人打得下去的时候啦。那么前面就可以一直填 s_1 直到 k 用尽了！

代码超级短的，甚至 D 代码都比它长。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,k;string s[N],ans;
bool cmp(string s1,string s2){
    return (s1+s2==s2+s1?s1<s2:s1+s2<s2+s1);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s+1,s+n+1,cmp);ans="";
    while(k>0&&ans.size()<s[1].size()){
        string tmp=s[1]+ans;k--;
        for(int i=2;i<=n;i++)tmp=min(tmp,s[i]+ans);ans=tmp;
    }
    while(k--)cout<<s[1];cout<<ans<<"\n";
    return 0;
}

最后求各位留一个小小的赞，真是太谢谢啦！