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

[[417678]]

题目

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

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

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

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

要求，字符串 需满足：

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

保证答案存在。

输入格式

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

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

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

输出格式

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

数据范围

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

输入样例：

 
 
 
    
  
  
  
  1. 4 
    2.   
  
  
  2. 3 3 
    3.   
  
  
  3. abc 
    4.   
  
  
  4. 3 2 
    5.   
  
  
  5. abc 
    6.   
  
  
  6. 3 3 
    7.   
  
  
  7. ayy 
    8.   
  
  
  8. 2 3 
    9.   
  
  
  9. ba 
    10.

输出样例：

 
 
 
    
  
  
  
  1. aca 
    2.   
  
  
  2. ac 
    3.   
  
  
  3. yaa 
    4.   
  
  
  4. baa 
    5.

思路：分情况讨论

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

代码

 
 
 
    
  
  
  
  1. #include  
    2.   
  
  
  2. #include  
    3.   
  
  
  3. #include  
    4.   
  
  
  4. using namespace std; 
    5.   
  
  
  5.  
    6.   
  
  
  6. int n, k; 
    7.   
  
  
  7. bool used[26]; 
    8.   
  
  
  8. string s, t; 
    9.   
  
  
  9.  
    10.   
  
  
  10. string tail() 
    11.   
  
  
  11. { 
    12.   
  
  
  12.     int i = 0; 
    13.   
  
  
  13.     for (; i < 26; ++ i) 
    14.   
  
  
  14.         if (used[i]) break; 
    15.   
  
  
  15.     char a = 'a' + i; 
    16.   
  
  
  16.     string res(k - n, a); 
    17.   
  
  
  17.     return res; 
    18.   
  
  
  18. } 
    19.   
  
  
  19.  
    20.   
  
  
  20. string get() 
    21.   
  
  
  21. { 
    22.   
  
  
  22.     char max_char; 
    23.   
  
  
  23.     for (int i = 25; i >= 0; -- i) 
    24.   
  
  
  24.     { 
    25.   
  
  
  25.         if (used[i]) 
    26.   
  
  
  26.         { 
    27.   
  
  
  27.             max_char = 'a' + i; 
    28.   
  
  
  28.             break; 
    29.   
  
  
  29.         } 
    30.   
  
  
  30.     } 
    31.   
  
  
  31.     char min_char; 
    32.   
  
  
  32.     for (int i = 0; i < 26; ++ i) 
    33.   
  
  
  33.     { 
    34.   
  
  
  34.         if (used[i]) 
    35.   
  
  
  35.         { 
    36.   
  
  
  36.             min_char = 'a' + i; 
    37.   
  
  
  37.             break; 
    38.   
  
  
  38.         } 
    39.   
  
  
  39.     } 
    40.   
  
  
  40.      
    41.   
  
  
  41.     int i = k - 1; 
    42.   
  
  
  42.     for (; i >= 0; -- i) 
    43.   
  
  
  43.     { 
    44.   
  
  
  44.         if (s[i] != max_char) break; 
    45.   
  
  
  45.     } 
    46.   
  
  
  46.      
    47.   
  
  
  47.     string res1 = s.substr(0, i); 
    48.   
  
  
  48.     string res2; 
    49.   
  
  
  49.     for (int j = s[i] - 'a' + 1; j < 26; ++ j) 
    50.   
  
  
  50.     { 
    51.   
  
  
  51.         if (used[j]) 
    52.   
  
  
  52.         { 
    53.   
  
  
  53.             res2 = (char) 'a' + j; 
    54.   
  
  
  54.             break; 
    55.   
  
  
  55.         } 
    56.   
  
  
  56.     } 
    57.   
  
  
  57.     string res3(k - i - 1, min_char); 
    58.   
  
  
  58.  
    59.   
  
  
  59.     return res1 + res2 + res3; 
    60.   
  
  
  60. } 
    61.   
  
  
  61.  
    62.   
  
  
  62. int main() 
    63.   
  
  
  63. { 
    64.   
  
  
  64.     int T; 
    65.   
  
  
  65.     cin >> T; 
    66.   
  
  
  66.     while (T --) 
    67.   
  
  
  67.     { 
    68.   
  
  
  68.         cin >> n >> k; 
    69.   
  
  
  69.         cin >> s; 
    70.   
  
  
  70.         memset(used, 0, sizeof used); 
    71.   
  
  
  71.         for (int i = 0; i < s.size(); ++ i) used[s[i] - 'a'] = true; 
    72.   
  
  
  72.         if (k > n) 
    73.   
  
  
  73.         { 
    74.   
  
  
  74.             t = s + tail(); 
    75.   
  
  
  75.         } 
    76.   
  
  
  76.         else 
    77.   
  
  
  77.         { 
    78.   
  
  
  78.             t = get(); 
    79.   
  
  
  79.         } 
    80.   
  
  
  80.         cout << t << endl; 
    81.   
  
  
  81.     } 
    82.   
  
  
  82. } 
    83.

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

y 总代码

看看 y 总的代码。

 
 
 
    
  
  
  
  1. #include  
    2.   
  
  
  2. #include  
    3.   
  
  
  3. #include  
    4.   
  
  
  4.  
    5.   
  
  
  5. using namespace std; 
    6.   
  
  
  6.  
    7.   
  
  
  7. const int N = 100010; 
    8.   
  
  
  8.  
    9.   
  
  
  9. int n, k; 
    10.   
  
  
  10. char s1[N], s2[N]; 
    11.   
  
  
  11. bool st[26]; 
    12.   
  
  
  12.  
    13.   
  
  
  13. char get_min() 
    14.   
  
  
  14. { 
    15.   
  
  
  15.     for (int i = 0; i < 26; i ++ ) 
    16.   
  
  
  16.         if (st[i]) 
    17.   
  
  
  17.             return i + 'a'; 
    18.   
  
  
  18.     return -1; 
    19.   
  
  
  19. } 
    20.   
  
  
  20.  
    21.   
  
  
  21. char get_next(int t) 
    22.   
  
  
  22. { 
    23.   
  
  
  23.     for (int i = t + 1; i < 26; i ++ ) 
    24.   
  
  
  24.         if (st[i]) 
    25.   
  
  
  25.             return i + 'a'; 
    26.   
  
  
  26.     return -1; 
    27.   
  
  
  27. } 
    28.   
  
  
  28.  
    29.   
  
  
  29. int main() 
    30.   
  
  
  30. { 
    31.   
  
  
  31.     int T; 
    32.   
  
  
  32.     scanf("%d", &T); 
    33.   
  
  
  33.     while (T -- ) 
    34.   
  
  
  34.     { 
    35.   
  
  
  35.         scanf("%d%d", &n, &k); 
    36.   
  
  
  36.         scanf("%s", s1); 
    37.   
  
  
  37.         memset(st, 0, sizeof st); 
    38.   
  
  
  38.         for (int i = 0; i < n; i ++ ) st[s1[i] - 'a'] = true; 
    39.   
  
  
  39.         if (k > n) 
    40.   
  
  
  40.         { 
    41.   
  
  
  41.             printf("%s", s1); 
    42.   
  
  
  42.             char c = get_min(); 
    43.   
  
  
  43.             for (int i = n; i < k; i ++ ) printf("%c", c); 
    44.   
  
  
  44.             puts(""); 
    45.   
  
  
  45.         } 
    46.   
  
  
  46.         else 
    47.   
  
  
  47.         { 
    48.   
  
  
  48.             s2[k] = 0; 
    49.   
  
  
  49.             for (int i = k - 1; i >= 0; i -- ) 
    50.   
  
  
  50.             { 
    51.   
  
  
  51.                 char c = get_next(s1[i] - 'a'); 
    52.   
  
  
  52.                 if (c != -1) 
    53.   
  
  
  53.                 { 
    54.   
  
  
  54.                     s2[i] = c; 
    55.   
  
  
  55.                     for (int j = 0; j < i; j ++ ) s2[j] = s1[j]; 
    56.   
  
  
  56.                     break; 
    57.   
  
  
  57.                 } 
    58.   
  
  
  58.                 s2[i] = get_min(); 
    59.   
  
  
  59.             } 
    60.   
  
  
  60.             puts(s2); 
    61.   
  
  
  61.         } 
    62.   
  
  
  62.     } 
    63.   
  
  
  63.  
    64.   
  
  
  64.     return 0; 
    65.   
  
  
  65. } 
    66.   
  
  
  66.  
    67.   
  
  
  67. // 作者：yxc 
    68.   
  
  
  68. // 链接：https://www.acwing.com/activity/content/code/content/1634481/ 
    69.   
  
  
  69. // 来源：AcWing 
    70.   
  
  
  70. // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 
    71.

很简洁。

经验：

  • 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/

 

网站题目：一道简单题看y总C++代码风格优于我自己的地方
当前URL：http://www.csdahua.cn/qtweb/news11/121361.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

定制开发知识

同城分类信息

成都户外广告　　 　江油做网站　　 　网站方案　　 　化妆品企业网站建设方案　　 　和正兴机械　　 　手机网站开发　　 　简阳网站建设　　 　佑馨产后护理　　 　成都帛金建站　　 　中国电信西部信息中心机房　　 　重庆企业网站建设　　 　上市集团网站建设　　 　网络营销　　 　网站定制　　 　南充机房托管　　 　德阳机房托管　　 　小谭网创广告　　 　绵阳网站制作　　 　传美奇电器　　 　四川雅安服务器托管