求问一道简单题,华为4.15机试分值100
6043
2022.04.15
2022.04.15
发布于 未知归属地

有N个工人来搬运M件货物,货物有相应的重量值
你需要找到一种方法来尽可能公平的分配货物,即“单个工人分到的货物重量”与“货物总重量/人数”的差值的平方和尽可能小,并输出这个平方和
举例,有2个人,分3件重量为[1,2,3]的货物,最公平的方案为[1,2],[3],与平均值的差值的平方和为0
PS:对所有的测试样例,总的货物重量都可以被人数整除
PS2:1<N<1000,1<M<10000,每件货物的重量范围在0~100
PS3:时间和空间限制开的很大所以可以不用管
样例输入:第一个数为人数N,第二个数为行李件数M,随后给出M个数,分别是每件货物对应的重量

2 3
1 2 3

样例输出

0

我那一团糟的思路是先排序,然后对每个工人,先从最重的开始分配,每次分配就将该件货物重量置为0表示已分配完成,超过平均值直接将差值的平方和加入结果,和平均值相等的继续,没超过的转头从前面开始找最小的,不断分配给这个工人直到他拿着的货物达到或者超过平均值,直到所有货物被分完,这时候如果仍然存在没有达到平均重量的工人,那么也计算差值的平方和加入结果 喜闻乐见的样例只过了20%(悲),存在的问题像是“5个工人分5件重量为【1,2,3,4,5】的货物”,如果按我的思路去弄的话会出现倒数第二个直接拿了【1,2】两件货物达到了平均值3,导致最后一个人手里没有货物,平方和会更大,我那思路没法处理这种边界条件肯定是错的 请各位大佬教教我吧呜呜呜

评论 (23)