建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
[[417678]]
題目
原題：AcWing 3805. 環(huán)形數(shù)組[1]
創(chuàng)新互聯(lián)專(zhuān)注為客戶(hù)提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都做網(wǎng)站、網(wǎng)站制作、房山網(wǎng)絡(luò)推廣、小程序開(kāi)發(fā)、房山網(wǎng)絡(luò)營(yíng)銷(xiāo)、房山企業(yè)策劃、房山品牌公關(guān)、搜索引擎seo、人物專(zhuān)訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供房山建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：www.cdcxhl.com
給定一個(gè)長(zhǎng)度為 的由小寫(xiě)字母構(gòu)成的字符串 。
請(qǐng)你構(gòu)造一個(gè)長(zhǎng)度為 的由小寫(xiě)字母構(gòu)成的字符串 。
要求，字符串 需滿(mǎn)足：
- 字符串 在字典序上大于字符串 。
- 字符串 的字母集是字符串 的字母集的子集。一個(gè)字符串的字母集是指該字符串包含的所有不同字母的集合，例如 abadaba 的字母集為 。
- 字符串 在字典序上盡可能小。
保證答案存在。
輸入格式
第一行包含整數(shù) ，表示共有 組測(cè)試數(shù)據(jù)。
每組數(shù)據(jù)第一行包含兩個(gè)整數(shù) 和 。
第二行包含一個(gè)長(zhǎng)度為 的字符串表示 。
輸出格式
每組數(shù)據(jù)輸出一行滿(mǎn)足所有條件的字符串 。
數(shù)據(jù)范圍
- 前三個(gè)測(cè)試點(diǎn)滿(mǎn)足 。
- 所有測(cè)試點(diǎn)滿(mǎn)足 ，。
- 同一測(cè)試點(diǎn)內(nèi)，所有 的和不超過(guò) ，所有 的和不超過(guò) 。
輸入樣例：
- 4
- 3 3
- abc
- 3 2
- abc
- 3 3
- ayy
- 2 3
- ba
輸出樣例：
- aca
- ac
- yaa
- baa
思路：分情況討論
- 當(dāng) k 大于 n 時(shí)，前 n 位不變，我們讓 n 位開(kāi)始填補(bǔ)出現(xiàn)過(guò)的最小字符就行
- 當(dāng) k 小于等于 n 時(shí)，我們從原字符串 k - 1 位開(kāi)始往前找，如果當(dāng)前字符還有變小的可能，那么就讓其變小，尋找停止，輸出新字符串
代碼
- #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;
- }
- }
可以看出我的代碼思路很清晰，但是寫(xiě)得有一點(diǎn)冗余。
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/
- // 來(lái)源：AcWing
- // 著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
很簡(jiǎn)潔。
經(jīng)驗(yàn)：
- char s[]; puts(s); 中， puts 遇到 \0 注意是 char s[k] = 0 而不是 char s[k] = '0' 字符串停止輸出。
參考資料
[1]AcWing 3805. 環(huán)形數(shù)組:
https://www.acwing.com/activity/content/problem/content/5457/
網(wǎng)頁(yè)題目：一道簡(jiǎn)單題看y總C++代碼風(fēng)格優(yōu)于我自己的地方
當(dāng)前網(wǎng)址：http://m.fisionsoft.com.cn/article/codphso.html
