UVa 1523 Helicopter

题目描述给定888个整数表示888位乘客的重量。直升机有888个座位分布在螺旋桨中心的周围每个座位的横向坐标和纵向坐标分别为−1-1−1、000或111且不包含(0,0)(0,0)(0,0)。规定左侧乘客产生正横向力矩右侧产生负横向力矩前方乘客产生正纵向力矩后方产生负纵向力矩。第iii个座位的横向力矩Mviwi⋅xiMv_i w_i \cdot x_iMvi​wi​⋅xi​纵向力矩Mhiwi⋅yiMh_i w_i \cdot y_iMhi​wi​⋅yi​其中(xi,yi)(x_i, y_i)(xi​,yi​)为座位的坐标wiw_iwi​为该座位乘客的重量。合力矩定义为M(∑i18Mvi)2(∑i18Mhi)2 M \sqrt{\left(\sum_{i1}^{8} Mv_i\right)^2 \left(\sum_{i1}^{8} Mh_i\right)^2}M(i1∑8​Mvi​)2(i1∑8​Mhi​)2​任务是将888个重量分配到888个座位上使得MMM最小。输入格式输入包含多个测试用例。每个测试用例为一行包含888个整数表示888位乘客的重量。输入以888个整数全为000的测试用例结束该用例不处理。输出格式对于每个测试用例输出一行包含一个实数表示最优安排下的合力矩MMM。结果保留333位小数。输出中不得包含多余空格或空行。样例输入1 2 3 4 5 6 7 8 0 0 0 0 0 0 0输出0.000题目分析本题的核心是给定888个重量值将它们一一映射到固定的888个坐标上使由重量和坐标共同决定的合力矩MMM最小。由于座位坐标固定每个乘客的力矩贡献只取决于其重量和所在座位的坐标。总横向力矩Sv∑wixiS_v \sum w_i x_iSv​∑wi​xi​总纵向力矩Sh∑wiyiS_h \sum w_i y_iSh​∑wi​yi​目标是最小化Sv2Sh2\sqrt{S_v^2 S_h^2}Sv2​Sh2​​。因为只有888个座位所有可能的分配方案数为8!403208! 403208!40320这个数量非常小完全可以通过暴力枚举所有排列来求解。每个测试用例只需枚举所有排列计算对应的SvS_vSv​和ShS_hSh​并更新最小值即可。本题没有隐藏的复杂性质直接枚举即可通过。时间复杂度和空间复杂度均很低。解题思路坐标定义将888个座位的坐标预先存储在数组中例如按顺序为(−1,−1)(-1,-1)(−1,−1)、(−1,0)(-1,0)(−1,0)、(−1,1)(-1,1)(−1,1)、(0,−1)(0,-1)(0,−1)、(0,1)(0,1)(0,1)、(1,−1)(1,-1)(1,−1)、(1,0)(1,0)(1,0)、(1,1)(1,1)(1,1)。这些坐标的横向值xxx和纵向值yyy分别表示座位相对螺旋桨的横向和纵向距离。枚举排列对每个测试用例读取888个重量后将重量数组排序便于使用std::next_permutation然后使用do-while循环遍历所有排列。对于每个排列将重量依次与预定义的坐标相乘累加得到SvS_vSv​和ShS_hSh​计算MSv2Sh2M \sqrt{S_v^2 S_h^2}MSv2​Sh2​​并与当前最优值比较保留较小者。精度处理由于坐标和重量均为整数SvS_vSv​和ShS_hSh​为整数MMM为浮点数。使用double类型存储输出时使用fixed和setprecision(3)保留三位小数。输入终止读取888个整数后检查是否全为000若是则结束循环。代码实现// Helicopter// UVa ID: 1523// Verdict: Accepted// Submission Date: 2026-06-20// UVa Run Time: 0.370s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 计算给定重量排列下的合力矩doublecalcMoment(constvectorintweights,constvectorpairint,intseats){intsumV0,sumH0;for(inti0;i8;i){sumVweights[i]*seats[i].first;sumHweights[i]*seats[i].second;}returnsqrt((double)sumV*sumV(double)sumH*sumH);}intmain(){// 8个座位的坐标相对于螺旋桨中心vectorpairint,intseats{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};vectorintweights(8);while(true){boolallZerotrue;for(inti0;i8;i){cinweights[i];if(weights[i]!0)allZerofalse;}if(allZero)break;// 结束标记sort(weights.begin(),weights.end());doublebest1e100;do{doublecurcalcMoment(weights,seats);if(curbest)bestcur;}while(next_permutation(weights.begin(),weights.end()));coutfixedsetprecision(3)bestendl;}return0;}总结本题是一个典型的全排列枚举问题数据规模极小8!403208! 403208!40320直接枚举即可。关键点在于正确理解力矩的计算方式并将每个座位的坐标与乘客重量对应。实际编程中使用std::next_permutation可以方便地遍历所有排列注意先对重量排序以确保遍历所有不同排列。时间复杂度为O(T⋅8!⋅8)O(T \cdot 8! \cdot 8)O(T⋅8!⋅8)其中TTT为测试用例数完全满足题目要求。此类问题提醒我们在数据范围较小时暴力枚举往往是最简单且高效的解决方法。