1 条题解

  • 0
    @ 2025-5-4 16:39:36
    #include <bits/stdc++.h>
    using namespace std;
    int n, ans;
    int a[1005];
    int cnt[5];
    int f[5][5]; // f[i][j]: i 区域有多少个 j
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            cnt[a[i]]++;
        }
        cnt[2] += cnt[1];
        cnt[3] += cnt[2];
        // 1: cnt[0]+1 ~ cnt[1]
        // 2: cnt[1]+1 ~ cnt[2]
        // 3: cnt[2]+1 ~ cnt[3]
        for (int i = 1; i <= 3; i++)
            for (int j = cnt[i - 1] + 1; j <= cnt[i]; j++)
                f[i][a[j]]++;
        int now;
        ans = 0;
        // 1 <-> 2
        now = min(f[1][2], f[2][1]);
        ans += now;
        f[1][2] -= now;
        f[2][1] -= now;
        // 2 <-> 3
        now = min(f[2][3], f[3][2]);
        ans += now;
        f[2][3] -= now;
        f[3][2] -= now;
        // 1 <-> 3
        now = min(f[1][3], f[3][1]);
        ans += now;
        f[1][3] -= now;
        f[3][1] -= now;
        // 三元交换
        now = 0;
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                if (i != j)
                    now += f[i][j];
        cout << ans + now / 3 * 2 << endl;
        return 0;
    }
    

    2.1.3 三值的排序 Sorting a Three-Valued Sequence

    信息

    ID
    947
    时间
    1000ms
    内存
    125MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者