企业官网建设流程全解析

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 最大 100000，log 约 30，整体运算量很小。

额外空间复杂度：
算法只使用了常数个变量来保存二分边界、剩余次数、累加结果等，没有使用与 n 或 m 成比例的额外数据结构。
因此额外空间复杂度为 O(1)。

Go完整代码如下：

packagemainimport("fmt""slices")funcmaxTotalValue(value,decay[]int,mint)(ansint){check:=func(lowint)bool{leftM:=mfori,v:=rangevalue{ifv>=low{leftM-=(v-low)/decay[i]+1ifleftM<0{// 提前跳出循环returntrue}}}returnfalse}low:=0ifcheck(0){left,right:=0,slices.Max(value)+1forleft+1<right{mid:=left+(right-left)/2ifcheck(mid){left=mid}else{right=mid}}low=left}// 计算价值严格大于 low 的价值和，以及这些价值的个数fori,v:=rangevalue{ifv>low{dec:=decay[i]k:=(v-low-1)/dec+1m-=k ans+=(v*2-dec*(k-1))*k}}ans/=2// 把除以 2 提到循环外面ans+=m*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):leftM=mforv,dinzip(value,decay):ifv>=low:leftM-=(v-low)//d+1ifleftM<0:returnTruereturnFalselow=0ifcheck(0):left,right=0,max(value)+1whileleft+1<right:mid=(left+right)//2ifcheck(mid):left=midelse:right=mid low=left ans=0forv,dinzip(value,decay):ifv>low:k=(v-low-1)//d+1m-=k ans+=(v*2-d*(k-1))*k ans//=2ans+=m*lowreturnans%1_000_000_007if__name__=="__main__":value=[6,5,4]decay=[2,1,1]m=4print(maxTotalValue(value,decay,m))

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;longlongmaxTotalValue(vector<int>&value,vector<int>&decay,intm){autocheck=[&](intlow)->bool{longlongleftM=m;for(size_t i=0;i<value.size();++i){intv=value[i];intd=decay[i];if(v>=low){leftM-=(v-low)/d+1;if(leftM<0){returntrue;}}}returnfalse;};intlow=0;if(check(0)){intleft=0;intright=*max_element(value.begin(),value.end())+1;while(left+1<right){intmid=left+(right-left)/2;if(check(mid)){left=mid;}else{right=mid;}}low=left;}longlongans=0;for(size_t i=0;i<value.size();++i){intv=value[i];intd=decay[i];if(v>low){intk=(v-low-1)/d+1;m-=k;ans+=((longlong)v*2-(longlong)d*(k-1))*k;}}ans/=2;ans+=(longlong)m*low;returnans%1000000007;}intmain(){vector<int>value={6,5,4};vector<int>decay={2,1,1};intm=4;longlongresult=maxTotalValue(value,decay,m);cout<<result<<endl;return0;}