原题:AcWing 3805. 环形数组[1]
给定一个长度为
的由小写字母构成的字符串
。
请你构造一个长度为
的由小写字母构成的字符串
。
要求,字符串
需满足:
在字典序上大于字符串
。
的字母集是字符串
的字母集的子集。一个字符串的字母集是指该字符串包含的所有不同字母的集合,例如 abadaba
的字母集为
。
在字典序上尽可能小。
保证答案存在。
第一行包含整数
,表示共有
组测试数据。
每组数据第一行包含两个整数
和
。
第二行包含一个长度为
的字符串表示
。
每组数据输出一行满足所有条件的字符串
。
。
,
。
的和不超过
,所有
的和不超过
。
4
3 3
abc
3 2
abc
3 3
ayy
2 3
ba
aca
ac
yaa
baa
思路:分情况讨论
#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 总的代码。
#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'
字符串停止输出。[1]
AcWing 3805. 环形数组: https://www.acwing.com/activity/content/problem/content/5457/