10665 Diatribe against Pigeonholes

題目連結

題目翻譯

有一排 N 個信箱（1 < N < 26），依序編號 1 到 N，分配給 N 位員工，員工依序以大寫字母 A, B, C, ... 表示。這排信箱架子在正中央（第 (N+1)/2 個位置附近）比較脆弱，因此包裹數量越多（越重）的員工，信箱要安排在離中間越遠的地方，藉此保護架子。所有包裹重量相同。每位員工收到的包裹數量，以一串大寫字母表示（用 # 結尾），字母出現的次數就是該員工收到的包裹數，不合法的字母需忽略。

請找出一種信箱安排方式，使得信箱裡的包裹數量符合「離中間越遠，包裹數不可以比較靠近中間的信箱少」的規則；如果有多種排法都滿足條件，輸出員工字母排列中，字典序最小的那一組。

輸入

第一行是測資數 M。每筆測資第一行是整數 N (1 < N < 26)；第二行是一串大寫字母，代表每位員工收到的包裹數量，以 # 結尾。

輸出

對每筆測資輸出兩行：第一行是信箱 1 到 N 由左到右對應的員工字母；第二行是對應信箱裡的包裹數量，皆以空白分隔。

解題思路

1. 先統計每位員工（A 到第 N 個字母，沒出現視為 0）收到的包裹數，並把所有數值由大到小排序。
2. 把信箱依照「離中間的距離」分組：距離相同的兩個信箱（例如左邊第 i 個、右邊第 i 個）為一組，由外到內共有 N/2 組；若 N 是奇數，正中央會多一個落單的信箱。離中間越遠的組別，必須分配到排序後越前面（數值越大）的兩個包裹數，因此把排序好的數列由外到內，依序每 2 個切成一組分給各組（正中央的落單信箱則分到排序後剩下的那一個，也就是最小值，符合「中間最輕」的要求）。
3. 同一組的兩個信箱因為離中間一樣遠，彼此之間沒有大小限制，所以該組的兩個包裹數可以自由分給左邊或右邊的信箱；當好幾個員工的包裹數相同時，這個「相同的值要分給哪個信箱」的自由度甚至會跨越不同組別。由於 N < 26，最多只有 12 組有這種左右可自由調換的情形，直接對所有「數值不同」的組別窮舉「左邊拿大的／右邊拿大的」兩種情況（最多 2^12 ≈ 4096 種組合），對每種組合推算出每個信箱「需要的包裹數」。
4. 包裹數決定後，同一個數值若對應到多個信箱，就把這些員工的字母由小到大排序，依信箱編號由小到大依序配對，這樣能保證字典序最小。
5. 最後在所有窮舉出來的結果中，取整體字串字典序最小的那一組作為答案。

程式碼

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define WA() cin.tie(0)->sync_with_stdio(0)

signed main() { WA();
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        string s; cin >> s;
        vector<int> w(n, 0);
        for (char c : s) if (c >= 'A' && c < 'A' + n) w[c - 'A']++;

        vector<int> sv = w;
        sort(all(sv), greater<int>());

        int k = n / 2;
        bool hasCenter = n % 2;
        vector<int> hi(k), lo(k);
        for (int i = 0; i < k; i++) { hi[i] = sv[2*i]; lo[i] = sv[2*i+1]; }
        int centerVal = hasCenter ? sv[2*k] : -1;

        vector<int> freeTier;
        for (int i = 0; i < k; i++) if (hi[i] != lo[i]) freeTier.pb(i);
        int fk = freeTier.size();

        map<int, vector<char> > valLet;
        for (int i = 0; i < n; i++) valLet[w[i]].pb('A' + i);

        string best; vector<int> bestVal;
        for (int mask = 0; mask < (1 << fk); mask++) {
            vector<int> b(k, 0);
            for (int j = 0; j < fk; j++) b[freeTier[j]] = (mask >> j) & 1;

            vector<int> posVal(n + 1, 0); // 1-indexed
            for (int i = 0; i < k; i++) {
                int L = i + 1, R = n - i;
                if (!b[i]) { posVal[L] = hi[i]; posVal[R] = lo[i]; }
                else { posVal[L] = lo[i]; posVal[R] = hi[i]; }
            }
            if (hasCenter) posVal[k + 1] = centerVal;

            map<int, vector<int> > valPos;
            for (int p = 1; p <= n; p++) valPos[posVal[p]].pb(p);

            vector<char> letter(n + 1);
            for (map<int, vector<int> >::iterator it = valPos.begin(); it != valPos.end(); ++it) {
                vector<int> &ps = it->second;
                vector<char> &ls = valLet[it->first];
                for (size_t i = 0; i < ps.size(); i++) letter[ps[i]] = ls[i];
            }

            string seq(n, ' ');
            for (int p = 1; p <= n; p++) seq[p-1] = letter[p];

            if (best.empty() || seq < best) {
                best = seq;
                bestVal.assign(posVal.begin() + 1, posVal.end());
            }
        }

        cout << best << '\n';
        for (int i = 0; i < n; i++) cout << bestVal[i] << " \n"[i == n-1];
    }
}