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

[[417678]]

题目

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

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

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

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

要求，字符串需满足：

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

保证答案存在。

输入格式

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

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

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

输出格式

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

数据范围

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

输入样例：

输出样例：

 
 
 
  
  
  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/

网站题目：一道简单题看y总C++代码风格优于我自己的地方
网页网址：http://www.shufengxianlan.com/qtweb/news11/121361.html

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

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

猜你还喜欢下面的内容