题目

原题：AcWing 3805. 环形数组[1]

给定一个长度为 的道简单题代码的地由小写字母构成的字符串 。

请你构造一个长度为 的总C自己由小写字母构成的字符串 。

要求，风格方字符串 需满足：

字符串 在字典序上大于字符串 。优于 字符串 的道简单题代码的地字母集是字符串 的字母集的子集。一个字符串的总C自己字母集是指该字符串包含的所有不同字母的集合，例如 abadaba 的风格方字母集为 。站群服务器 字符串 在字典序上尽可能小。优于

保证答案存在。道简单题代码的地

输入格式

第一行包含整数 ，总C自己表示共有 组测试数据。风格方

每组数据第一行包含两个整数 和 。优于

第二行包含一个长度为 的道简单题代码的地字符串表示 。

输出格式

每组数据输出一行满足所有条件的总C自己字符串 。

数据范围

前三个测试点满足 。风格方 所有测试点满足 ，。 同一测试点内，所有 的和不超过 ，所有 的和不超过 。

输入样例：

4 3 3 abc 3 2 abc 3 3 ayy 2 3 ba 

输出样例：

aca ac yaa baa 

思路：分情况讨论

当 k 大于 n 时，前 n 位不变，免费源码下载我们让 n 位开始填补出现过的最小字符就行 当 k 小于等于 n 时，我们从原字符串 k - 1 位开始往前找，如果当前字符还有变小的可能，那么就让其变小，寻找停止，输出新字符串

代码

#include <iostream> #include <cstring> #include <algorithm> using namespace std; int n, k; bool used[26]; string s, t; string tail() {     int i = 0;     for (; i < 26; ++ i)         if (used[i]) break;     char a = a + i;     string res(k - n, a);     return res; } string get() {     char max_char;     for (int i = 25; i >= 0; -- i)     {         if (used[i])         {             max_char = a + i;             break;         }     }     char min_char;     for (int i = 0; i < 26; ++ i)     {         if (used[i])         {             min_char = a + i;             break;         }     }     int i = k - 1;     for (; i >= 0; -- i)     {         if (s[i] != max_char) break;     }     string res1 = s.substr(0, i);     string res2;     for (int j = s[i] - a + 1; j < 26; ++ j)     {         if (used[j])         {             res2 = (char) a + j;             break;         }     }     string res3(k - i - 1, min_char);     return res1 + res2 + res3; } int main() {     int T;     cin >> T;     while (T --)     {         cin >> n >> k;         cin >> s;         memset(used, 0, sizeof used);         for (int i = 0; i < s.size(); ++ i) used[s[i] - a] = true;         if (k > n)         {             t = s + tail();         }         else         {             t = get();         }         cout << t << endl;     } } 

可以看出我的代码思路很清晰，但是写得有一点冗余。

y 总代码

看看 y 总的代码。

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int n, k; char s1[N], s2[N]; bool st[26]; char get_min() {     for (int i = 0; i < 26; i ++ )         if (st[i])             return i + a;     return -1; } char get_next(int t) {     for (int i = t + 1; i < 26; i ++ )         if (st[i])             return i + a;     return -1; } int main() {     int T;     scanf("%d", &T);     while (T -- )     {         scanf("%d%d", &n, &k);         scanf("%s", s1);         memset(st, 0, sizeof st);         for (int i = 0; i < n; i ++ ) st[s1[i] - a] = true;         if (k > n)         {             printf("%s", s1);             char c = get_min();             for (int i = n; i < k; i ++ ) printf("%c", c);             puts("");         }         else         {             s2[k] = 0;             for (int i = k - 1; i >= 0; i -- )             {                 char c = get_next(s1[i] - a);                 if (c != -1)                 {                     s2[i] = c;                     for (int j = 0; j < i; j ++ ) s2[j] = s1[j];                     break;                 }                 s2[i] = get_min();             }             puts(s2);         }     }     return 0; } // 作者：yxc // 链接：https://www.acwing.com/activity/content/code/content/1634481/ // 来源：AcWing // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

很简洁。

经验：

char s[]; puts(s); 中， puts 遇到 \0 注意是 char s[k] = 0 而不是 char s[k] = 0 字符串停止输出。WordPress模板

参考资料

[1]AcWing 3805. 环形数组:

https://www.acwing.com/activity/content/problem/content/5457/