Balanced Ternary String

給你一個長度為$n$，只有$0, 1, 2$三種字元的字串。請你把字串做調整，使得每個字符都只出現$\frac n 3$次的情況下，字典順序最小。

題解

既然字典序要盡量小，那就是0要盡量前面，2要盡量後面。

所以對於

  1. 少2的情況，我們就從後面換回來，有得換就換。畢竟是0或1換2，都是變差，先換誰無所謂，總之就是能把越後面換成2，對於字典序影響就會越小。
  2. 少0的情況，我們就從前面換過來，有得換就換。畢竟能把1或2換成0，都是變好了，能換就趕快換。
  3. 少1的話，如果是用0來換，從後面換回來，如果是用2來換，就從前面換回來。

一切以影響力進行思考就對啦！

至於實作，可以寫成function，來簡化重複的code…

AC Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    int n;
    scanf("%d", &n);
    char inp[n + 3];
    scanf("%s", inp);

    int cnt[3] = {0};
    for (int i = 0; i < n; i++)
        cnt[inp[i] - '0']++;

    // 2 missing
    // we replace from the back -> as back as possible
    for (int i = n - 1; i >= 0 && cnt[2] < n / 3; i--) {
        if (inp[i] == '0' && cnt[0] > n / 3) {
            cnt[2]++;
            cnt[0]--;
            inp[i] = '2';
        } else if (inp[i] == '1' && cnt[1] > n / 3) {
            cnt[2]++;
            cnt[1]--;
            inp[i] = '2';
        }
    }

    // 0 missing
    // we replace from the front, as front as possible
    for (int i = 0; i < n && cnt[0] < n / 3; i++) {
        if (inp[i] == '1' && cnt[1] > n / 3) {
            cnt[0]++;
            cnt[1]--;
            inp[i] = '0';
        } else if (inp[i] == '2' && cnt[2] > n / 3) {
            cnt[0]++;
            cnt[2]--;
            inp[i] = '0';
        }
    }

    // 1 missing
    // sub 0 with 1 from the back
    for (int i = n - 1; i >= 0 && cnt[1] < n / 3; i--) {
        if (inp[i] == '0' && cnt[0] > n / 3) {
            cnt[0]--;
            cnt[1]++;
            inp[i] = '1';
        }
    }

    // sub 2 with 1 from the front
    for (int i = 0; i < n && cnt[1] < n / 3; i++) {
        if (inp[i] == '2' && cnt[2] > n / 3) {
            cnt[2]--;
            cnt[1]++;
            inp[i] = '1';
        }
    }

    printf("%s\n", inp);

    return 0;
}