企业官网建设流程全解析

题目描述

给定888个整数，表示888位乘客的重量。直升机有888个座位，分布在螺旋桨（中心）的周围，每个座位的横向坐标和纵向坐标分别为−1-1−1、000或111，且不包含(0,0)(0,0)(0,0)。规定左侧乘客产生正横向力矩，右侧产生负横向力矩；前方乘客产生正纵向力矩，后方产生负纵向力矩。第iii个座位的横向力矩Mvi=wi⋅xiMv_i = w_i \cdot x_iMvi​=wi​⋅xi​，纵向力矩Mhi=wi⋅yiMh_i = w_i \cdot y_iMhi​=wi​⋅yi​，其中(xi,yi)(x_i, y_i)(xi​,yi​)为座位的坐标，wiw_iwi​为该座位乘客的重量。合力矩定义为：

M=(∑i=18Mvi)2+(∑i=18Mhi)2 M = \sqrt{\left(\sum_{i=1}^{8} Mv_i\right)^2 + \left(\sum_{i=1}^{8} Mh_i\right)^2}M=(i=1∑8​Mvi​)2+(i=1∑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​，目标是最小化Sv2+Sh2\sqrt{S_v^2 + S_h^2}Sv2​+Sh2​​。

因为只有888个座位，所有可能的分配方案数为8!=403208! = 403208!=40320，这个数量非常小，完全可以通过暴力枚举所有排列来求解。每个测试用例只需枚举所有排列，计算对应的SvS_vSv​和ShS_hSh​，并更新最小值即可。

本题没有隐藏的复杂性质，直接枚举即可通过。时间复杂度和空间复杂度均很低。

解题思路

1. 坐标定义：将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分别表示座位相对螺旋桨的横向和纵向距离。

2. 枚举排列：对每个测试用例，读取888个重量后，将重量数组排序（便于使用std::next_permutation），然后使用do-while循环遍历所有排列。对于每个排列，将重量依次与预定义的坐标相乘，累加得到SvS_vSv​和ShS_hSh​，计算M=Sv2+Sh2M = \sqrt{S_v^2 + S_h^2}M=Sv2​+Sh2​​，并与当前最优值比较，保留较小者。

3. 精度处理：由于坐标和重量均为整数，SvS_vSv​和ShS_hSh​为整数，MMM为浮点数。使用double类型存储，输出时使用fixed和setprecision(3)保留三位小数。

4. 输入终止：读取888个整数后，检查是否全为000，若是则结束循环。

代码实现

// Helicopter// UVa ID: 1523// Verdict: Accepted// Submission Date: 2026-06-20// UVa Run Time: 0.370s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 计算给定重量排列下的合力矩doublecalcMoment(constvector<int>&weights,constvector<pair<int,int>>&seats){intsumV=0,sumH=0;for(inti=0;i<8;++i){sumV+=weights[i]*seats[i].first;sumH+=weights[i]*seats[i].second;}returnsqrt((double)sumV*sumV+(double)sumH*sumH);}intmain(){// 8个座位的坐标（相对于螺旋桨中心）vector<pair<int,int>>seats={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};vector<int>weights(8);while(true){boolallZero=true;for(inti=0;i<8;++i){cin>>weights[i];if(weights[i]!=0)allZero=false;}if(allZero)break;// 结束标记sort(weights.begin(),weights.end());doublebest=1e100;do{doublecur=calcMoment(weights,seats);if(cur<best)best=cur;}while(next_permutation(weights.begin(),weights.end()));cout<<fixed<<setprecision(3)<<best<<endl;}return0;}

总结

本题是一个典型的全排列枚举问题，数据规模极小（8!=403208! = 403208!=40320），直接枚举即可。关键点在于正确理解力矩的计算方式，并将每个座位的坐标与乘客重量对应。实际编程中，使用std::next_permutation可以方便地遍历所有排列，注意先对重量排序以确保遍历所有不同排列。时间复杂度为O(T⋅8!⋅8)O(T \cdot 8! \cdot 8)O(T⋅8!⋅8)，其中TTT为测试用例数，完全满足题目要求。此类问题提醒我们，在数据范围较小时，暴力枚举往往是最简单且高效的解决方法。