[[417678]]

題目

原題：AcWing 3805. 環形數組[1]

給定一個長度為 的由小寫字母構成的字符串 。

請你構造一個長度為 的由小寫字母構成的字符串 。

要求，字符串 需滿足：

• 字符串 在字典序上大于字符串 。
• 字符串 的字母集是字符串 的字母集的子集。一個字符串的字母集是指該字符串包含的所有不同字母的集合，例如 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 <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 總代碼

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