您现在的位置是：亿华云 > 域名

一道简单题看 y 总 C++ 代码风格优于我自己的地方

亿华云2025-10-03 22:30:04【域名】1人已围观

简介题目原题：AcWing 3805. 环形数组[1]给定一个长度为的由小写字母构成的字符串。请你构造一个长度为的由小写字母构成的字符串。要求，字符串需满足：字符串在字典序上大于字符串。

题目

原题：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 // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

很简洁。