带k转移系数的数组均等分配最小工作值求解及二分法超时优化
问题核心与原代码失效原因
场景的数学本质
先把操作规则拆透,避免被错误的配对思路带偏:
- 从学生i处转出工作量x(x≥0,非负转出才有意义),该学生最终工作量为
a[i] - x。 - 转出的x转给任意学生j,学生j的工作量增加
x*k,最终为a[j] + x*k。 - 所有学生最终工作量要统一为T,最优解里不存在“同一个学生既转出又接收”的无效操作,因此每个学生只有三种状态:
- 初始值a[i] > T:必须是转出方,需要转出的固定值为
a[i] - T(转出后刚好降到T,接收的话会让值更高,离T更远,无意义)。 - 初始值a[i] < T:必须是接收方,最终需要的工作量增量为
T - a[i],换算成需要接收的转账量为(T - a[i])/k(转出的话会让值更低,离T更远,无意义)。 - 初始值a[i] = T:既不转出也不接收,对平衡无贡献。
- 初始值a[i] > T:必须是转出方,需要转出的固定值为
- 全局必须满足的硬约束:所有转出方累计转出的总工作量,等于所有接收方累计需要收到的总转账量——因为每一笔转账都会从转出方扣除x,给接收方带来x*k的增益,两边总量必须匹配才能让所有人刚好到T。
原代码超时/逻辑错误的根源
- 适配场景错位:原代码用双指针两两配对凑
a[i] + k*a[j] = (k+1)*mid的逻辑,是从n=2的解方程场景硬套来的,根本不适用于n≥3的情况——n>2时转出方可以同时给多个接收方转账,不需要两两绑定配对,这套配对逻辑和全局平衡约束完全脱节,甚至会因为判定逻辑和实际场景不匹配,导致二分方向走偏。 - 终止条件有精度缺陷:用浮点数
while(low <= high)做循环判定,浮点数本身存在精度误差,永远不会精准满足low=high的终止条件,会陷入无限循环直到触发超时。 - 平衡判定维度缺失:没有计算全局的转出总量和接收总需求,而是靠局部的两两配对等式判定,完全没法覆盖多对多的转账场景,结果也不可靠。
通用n>2的求解思路
直接基于全局平衡约束做二分搜索,时间复杂度低到完全不会触发超时:
- 确定二分的上下界
- 下界low:数组的最小值
min(A)——T不可能比所有元素的初始值更低,毕竟我们没有办法凭空减少所有人的工作量,最多就是不需要任何转账,所有人停在初始最小值的水平。 - 上界high:数组的最大值
max(A)——T不可能比所有元素的初始值更高,转账本身是有增益换算比例的,不可能把所有人的工作量拉到比初始最高值还高。
- 下界low:数组的最小值
- 设计单次判定逻辑(给定一个候选T,判断是否可以通过合法转账达到平衡)
一次遍历数组累计两个全局值:- 累计总转出量
total_out:所有a[i] > T的元素,累加a[i] - T,也就是把所有超T的部分全部拿出来的总规模。 - 累计接收方总缺口
total_gap:所有a[i] < T的元素,累加T - a[i],也就是所有接收方离目标T还差的总工作量规模。
基于两个值判定二分方向: - 如果
k * total_out > total_gap:说明把所有超T的部分全部转出去产生的总增益,已经超过了接收方的总缺口——当前的T定低了,我们可以把T往更高的方向调整,对应的把low移到mid。 - 如果
k * total_out < total_gap:说明哪怕把所有超T的部分全部转出去产生的总增益,都填不满接收方的缺口——当前的T定高了,需要把T往下调,对应的把high移到mid。 - 如果两者相等,这个T就是我们要找的目标值。
- 累计总转出量
- 彻底解决超时问题的循环设置
不要用带精度误差的浮点终止条件,直接固定迭代100次二分就够了:每次二分都会把搜索区间缩小一半,100次迭代之后的精度差是初始区间长度的1/2^100,远高于保留两位小数的要求,完全不会出现死循环。
整体时间复杂度是O(100 * n),哪怕n到1e5的规模都能毫秒级跑完。
针对原代码的修正参考示例
double solve(vector<int>& a, double k) { sort(a.begin(), a.end()); double low = a[0], high = a.back(); // 固定跑100次迭代,彻底避免浮点死循环 for(int iter = 0; iter < 100; iter++) { double mid = (low + high) / 2; double total_out = 0, total_gap = 0; for(auto num : a) { if(num > mid) total_out += num - mid; if(num < mid) total_gap += mid - num; } if(k * total_out < total_gap) { // T定高了,往下调 high = mid; } else { // T定低了,往上调 low = mid; } } // 保留两位小数返回 return round(low * 100) / 100; }
内容的提问来源于stack exchange,提问作者meenu。
相关产品推荐
相关产品推荐

