题目描述题目要求将SSS个标本分配到CCC个离心机室中每个室最多可以容纳000、111或222个标本。分配的目标是最小化不平衡度IMBALANCE\textit{IMBALANCE}IMBALANCE其定义为IMBALANCE∑i1C∣CMi−AM∣ \textit{IMBALANCE} \sum_{i 1}^{C} |\textit{CM}_i - \textit{AM}|IMBALANCEi1∑C​∣CMi​−AM∣其中CMi\textit{CM}_iCMi​是第iii个室的总质量即分配到该室的标本质量之和。AM\textit{AM}AM是所有室的平均质量即所有标本总质量除以室数CCC。输入格式输入包含多组数据。每组数据格式如下第一行包含两个整数CCC和SSS1≤C≤51 \le C \le 51≤C≤51≤S≤2C1 \le S \le 2C1≤S≤2C分别表示室数和标本数。第二行包含SSS个整数表示每个标本的质量111到100010001000之间由空格分隔。输出格式对于每组数据首先输出一行Set #X其中XXX从111开始递增。接下来输出CCC行每行格式为室号第111列、冒号第222列、然后从第444列开始输出该室分配的标本质量质量之间用恰好一个空格分隔。如果某室没有分配标本则只输出室号和冒号不输出质量。最后输出一行IMBALANCE X其中XXX为计算出的不平衡度保留555位小数。每组输出后跟一个空行。样例输入2 3 6 3 8 3 5 51 19 27 14 33 5 9 1 2 3 5 7 11 13 17 19输出Set #1 0: 6 3 1: 8 IMBALANCE 1.00000 Set #2 0: 51 1: 19 27 2: 14 33 IMBALANCE 6.00000 Set #3 0: 1 17 1: 2 13 2: 3 11 3: 5 7 4: 19 IMBALANCE 11.60000题目分析本题的核心是将SSS个标本分配到CCC个室中每个室最多222个标本使得各室总质量与平均质量之差的绝对值之和最小。问题转化由于每个室最多放222个标本且S≤2CS \le 2CS≤2C因此有些室可能只放111个标本或空置。为了简化处理可以引入质量为000的虚拟标本使得标本总数恰好为2C2C2C。这样每个室恰好分配到222个标本允许质量为000问题转化为将2C2C2C个标本包含虚拟的000两两配对使得各对质量和与平均质量之差的绝对值之和最小。最优配对策略已知一个经典结论对于此类两两配对使各对和尽量接近的问题最优策略是将标本质量排序后将最小的与最大的配对次小的与次大的配对依此类推。这是因为这种配对方式能够平衡各对的和使它们尽可能接近。具体步骤如下将所有标本质量包括补充的000按升序排序。将第iii小的与第iii大的配对即masses[i]\textit{masses}[i]masses[i]与masses[2C−1−i]\textit{masses}[2C - 1 - i]masses[2C−1−i]配对iii从000到C−1C-1C−1。计算每个配对的和然后计算与平均质量AMAMAM的差的绝对值累加得到IMBALANCE\textit{IMBALANCE}IMBALANCE。平均质量的计算平均质量AMAMAM定义为所有标本总质量除以室数CCC。注意虚拟标本的质量000不计入总质量因此总质量即为原始标本质量之和。输出格式每个室输出时需要按升序输出该室的两个标本质量小的在前大的在后。由于配对时masses[i]≤masses[2C−1−i]\textit{masses}[i] \le \textit{masses}[2C - 1 - i]masses[i]≤masses[2C−1−i]因此可以直接先输出masses[i]\textit{masses}[i]masses[i]再输出masses[2C−1−i]\textit{masses}[2C - 1 - i]masses[2C−1−i]。注意质量为000的虚拟标本不应输出。边界情况如果S2CS 2CS2C则需要补充2C−S2C - S2C−S个000。如果某室的两个标本质量均为000则该室不输出任何质量只输出室号和冒号。不平衡度需要保留555位小数。复杂度分析每组数据排序复杂度O(2Clog⁡(2C))O(2C \log(2C))O(2Clog(2C))C≤5C \le 5C≤5可忽略。总复杂度O(T×Clog⁡C)O(T \times C \log C)O(T×ClogC)。代码实现// Station Balance// UVa ID: 410// Verdict: Accepted// Submission Date: 2016-07-24// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net//// http://www.algorithmist.com/index.php/UVa_410#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intchambers,specimens,mass,cases0;while(cinchambersspecimens){inttotal_masses0;vectorintmasses;for(inti1;ispecimens;i){cinmass;masses.push_back(mass);total_massesmass;}while(masses.size()2*chambers)masses.push_back(0);sort(masses.begin(),masses.end());intaverage_masses0;coutSet #cases\n;for(inti0;ichambers;i){cout i:;intamasses[i],bmasses[2*chambers-1-i];if(a0||b0){if(a0)cout a;if(b0)cout b;}cout\n;average_massesabs((ab)*chambers-total_masses);}coutIMBALANCE ;coutfixedsetprecision(5)(double)average_masses/(double)chambers;cout\n\n;}return0;}