UVa 410 Station Balance：貪心策略最小化離心機不平衡度

問題模型

C 個腔室，每室最多放 2 個標本。S 個標本質量已知。需分配使 **IMBALANCE = Σ |CM_i - AM|** 最小，其中 CM_i 為第 i 室標本質量和，AM = 總質量 / C。

貪心證明

排序質量。若 S ≤ C，每室放 1 個。
若 S > C，必有 2C - S 個腔室放 2 個，其餘放 1 個。
**最優策略**：最大的 2C-S 個標本**單獨佔室**；剩餘標本**兩頭配對**（最小+最大、次小+次大…），放入剩餘腔室。此策略使每室質量和最接近平均值。

算法步驟

1. 讀入 C, S，質量數組 m[]，升序排序。
2. 計算 AM = sum(m)/C。
3. 初始化 chamber[C] 為空向量，CM[C]=0。
4. idx=0：
    若 S ≤ C：依次每室放一個。
    否則：前 2C-S 個大質量各自佔室（idx 從末尾遞減）。
5. 剩餘標本雙指針 l=0, r=idx，配對放入剩餘腔室：
   chamber[i].push_back(m[l++]); chamber[i].push_back(m[r--]);
6. 計算 IMBALANCE = Σ |CM_i - AM|，輸出格式化結果。

核心代碼

#include 
using namespace std;

int main(){
    int C, S, tc=1;
    while(cin>>C>>S){
        vector m(S);
        double sum=0;
        for(int& x:m){ cin>>x; sum+=x; }
        sort(m.begin(), m.end());
        double AM = sum/C;
        vector> ch(C);
        vector cm(C,0);
        int idx = S-1;
        if(S <= C){
            for(int i=0;i

樣例驗證
輸入:
2 3
6 3 8
3 5
51 19 27 14 33
5 9
1 2 3 5 7 11 13 17 19

輸出與題目樣例完全一致。