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

[[417678]]

题目

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

创新互联专注为客户提供全方位的互联网综合服务，包含不限于成都做网站、网站制作、房山网络推广、小程序开发、房山网络营销、房山企业策划、房山品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联为所有大学生创业者提供房山建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

给定一个长度为 的由小写字母构成的字符串 。

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

要求，字符串 需满足：

• 字符串 在字典序上大于字符串 。
• 字符串 的字母集是字符串 的字母集的子集。一个字符串的字母集是指该字符串包含的所有不同字母的集合，例如 abadaba 的字母集为 。
• 字符串 在字典序上尽可能小。

保证答案存在。

输入格式

第一行包含整数 ，表示共有 组测试数据。

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

第二行包含一个长度为 的字符串表示 。

输出格式

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

数据范围

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

输入样例：

 
 
 

  
  
  
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  
  
  
  
#include  
  
  
  
#include  
  
  
  
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  
  
  
  
#include  
  
  
  
#include  
  
  
  
 
  
  
  
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/