2026-09-28最大总价值。用go语言现有两个整数数组 value、decay以及一个整数 m。value 中第 i 个元素表示编号 i 这个选项第一次被选中时能带来的基础收益decay 中第 i 个元素表示编号 i 每被再次选中一次其单次收益会下降多少。你可以从任意编号中反复选择但全部选择动作加起来不能超过 m 次。对于编号 i如果它被选中的次数记为第 t 次t 从 1 开始计数那么这一次产生的收益是 value[i] 减去 decay[i] 乘以 (t - 1)。请计算在最多选择 m 次的情况下能够取得的累计收益最大值。因为最终数值可能很大所以把该最大值对 1,000,000,007 取余后返回。1 value.length decay.length 100000。1 value[i], decay[i] 1000000000。1 m 1000000000。输入 value [6,5,4], decay [2,1,1], m 4。输出 19。解释一种最优选择序列如下选择下标 0获得的价值为 6。选择下标 1获得的价值为 5。选择下标 2获得的价值为 4。再次选择下标 0获得的价值为 6 - 2 4。总价值为 6 5 4 4 19。在至多 4 次选择中没有其他选择序列能获得更高的总价值。题目来自力扣3971。大体步骤如下第一步把问题转化为“取前 m 大值”每个下标 i 都能产生一个等差数列第 1 次value[i]第 2 次value[i] - decay[i]第 3 次value[i] - 2 * decay[i]……这些值随着选择次数增加而不断减小。因为每次选择都是独立的并且选了一个值之后该下标的下一个值会变小所以最优策略就是不断取当前全局最大的单次收益。因此问题等价于把所有下标产生的所有可能收益放在一起取最大的 m 个如果总可用次数不足 m就全取非负的求和。第二步二分寻找第 m 大的收益阈值 low由于 m 可能非常大不能直接模拟取 m 次。代码使用二分查找来确定一个阈值 low。定义一个检查函数给定一个阈值 x统计所有序列中单次收益大于等于 x 的项一共有多少个。对于某个下标 i如果 value[i] 已经小于 x那么这条序列没有任何项大于等于 x。如果 value[i] x那么这条序列中满足 value[i] - decay[i] * (t - 1) x 的项数 t 为floor((value[i] - x) / decay[i]) 1。把所有下标的这个数量加起来如果总和超过 m说明收益大于等于 x 的项太多了阈值 x 还可以再大一点如果总和不超过 m说明阈值 x 太大了。二分范围从 0 到 max(value) 1寻找最大的 x使得“收益大于等于 x 的项数总和 m”。把这个最大的 x 记为 low。如果连 x 0 都不满足“收益大于等于 0 的项数总和 m”说明所有非负收益的项加起来都不超过 m此时 low 保持为 0。经过这一步可以得到一个关键性质所有收益严格大于 low 的项总数一定不超过 m而所有收益大于等于 low 的项总数一定超过 m。因此第 m 大的收益值就是 low或者至少可以说所有大于 low 的收益都应该被选走剩下的次数用价值等于 low 的项来补足。第三步累加所有收益严格大于 low 的项遍历每个下标 i。如果 value[i] low计算这条序列中收益严格大于 low 的项数 k。因为收益序列是 value[i], value[i] - decay[i], value[i] - 2 * decay[i], …最后一个大于 low 的项满足 value[i] - decay[i] * (k - 1) low。所以 k floor((value[i] - low - 1) / decay[i]) 1。这些 k 个项全部会被选中。它们的和是一个等差数列首项是 value[i]末项是 value[i] - decay[i] * (k - 1)项数是 k。等差数列求和为k * (首项 末项) / 2。代码中先累加 k * (2 * value[i] - decay[i] * (k - 1))最后再统一除以 2。每处理一个下标就把总剩余可选次数 m 减去 k。第四步用剩余次数选择价值等于 low 的项处理完所有大于 low 的项后剩余的可选次数记为 m。因为所有大于 low 的项都已经选完而总的大于等于 low 的项数超过原来的 m所以剩下的次数一定可以全部选到价值恰好等于 low 的项。这些项可能来自多个不同的下标但每个的价值都是 low。因此直接把“剩余次数 * low”加到总收益中即可。第五步取模并返回由于总收益可能非常大最后把结果对 1,000,000,007 取模后返回。代码中的累加过程先不除以 2最后统一除以 2再乘剩余次数与 low最后取模。关于正确性因为所有收益序列都是递减的全局最优选择就是不断取当前最大的单次收益。二分找到的 low 实际上就是第 m 大收益附近的阈值。所有大于 low 的收益一定在前 m 大之内必须全选等于 low 的收益用来补足剩余次数小于 low 的收益不会被选中。因此该算法能得到最大总价值。关于特殊情况如果所有非负收益的项数加起来都不超过 m那么 low 会是 0。此时所有正收益的项都会被选中剩余次数乘以 0相当于不选负收益符合“最多选 m 次”的题意。时间复杂度二分查找的轮数是 O(log(max(value)))其中 max(value) 最大为 10^9所以大约 30 轮。每一轮检查都需要遍历所有 n 个下标时间复杂度 O(n)。二分结束后还需要再遍历一次所有下标来累加收益也是 O(n)。因此总时间复杂度为 O(n * log(max(value)))。由于 n 最大 100000log 约 30整体运算量很小。额外空间复杂度算法只使用了常数个变量来保存二分边界、剩余次数、累加结果等没有使用与 n 或 m 成比例的额外数据结构。因此额外空间复杂度为 O(1)。Go完整代码如下packagemainimport(fmtslices)funcmaxTotalValue(value,decay[]int,mint)(ansint){check:func(lowint)bool{leftM:mfori,v:rangevalue{ifvlow{leftM-(v-low)/decay[i]1ifleftM0{// 提前跳出循环returntrue}}}returnfalse}low:0ifcheck(0){left,right:0,slices.Max(value)1forleft1right{mid:left(right-left)/2ifcheck(mid){leftmid}else{rightmid}}lowleft}// 计算价值严格大于 low 的价值和以及这些价值的个数fori,v:rangevalue{ifvlow{dec:decay[i]k:(v-low-1)/dec1m-k ans(v*2-dec*(k-1))*k}}ans/2// 把除以 2 提到循环外面ansm*low// 剩余 m 次选的价值都是 lowreturnans%1_000_000_007}funcmain(){value:[]int{6,5,4}decay:[]int{2,1,1}m:4result:maxTotalValue(value,decay,m)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defmaxTotalValue(value,decay,m):defcheck(low):leftMmforv,dinzip(value,decay):ifvlow:leftM-(v-low)//d1ifleftM0:returnTruereturnFalselow0ifcheck(0):left,right0,max(value)1whileleft1right:mid(leftright)//2ifcheck(mid):leftmidelse:rightmid lowleft ans0forv,dinzip(value,decay):ifvlow:k(v-low-1)//d1m-k ans(v*2-d*(k-1))*k ans//2ansm*lowreturnans%1_000_000_007if__name____main__:value[6,5,4]decay[2,1,1]m4print(maxTotalValue(value,decay,m))C完整代码如下#includeiostream#includevector#includealgorithmusingnamespacestd;longlongmaxTotalValue(vectorintvalue,vectorintdecay,intm){autocheck[](intlow)-bool{longlongleftMm;for(size_t i0;ivalue.size();i){intvvalue[i];intddecay[i];if(vlow){leftM-(v-low)/d1;if(leftM0){returntrue;}}}returnfalse;};intlow0;if(check(0)){intleft0;intright*max_element(value.begin(),value.end())1;while(left1right){intmidleft(right-left)/2;if(check(mid)){leftmid;}else{rightmid;}}lowleft;}longlongans0;for(size_t i0;ivalue.size();i){intvvalue[i];intddecay[i];if(vlow){intk(v-low-1)/d1;m-k;ans((longlong)v*2-(longlong)d*(k-1))*k;}}ans/2;ans(longlong)m*low;returnans%1000000007;}intmain(){vectorintvalue{6,5,4};vectorintdecay{2,1,1};intm4;longlongresultmaxTotalValue(value,decay,m);coutresultendl;return0;}