2026-09-28：最大总价值。用go语言，现有两个整数数组 value、decay，以及一个整数 m。value 中第 i 个元素表示编号 i 这个选项第一次被

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完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func maxTotalValue(value, decay []int, m int) (ans int) {
    check := func(low int)bool {
        leftM := m
        for i, v := range value {
            if v >= low {
                leftM -= (v-low)/decay[i] + 1
                if leftM < 0 { // 提前跳出循环
                    returntrue
                }
            }
        }
        returnfalse
    }

low := 0
    if check(0) {
        left, right := 0, slices.Max(value)+1
        for left+1 < right {
            mid := left + (right-left)/2
            if check(mid) {
                left = mid
            } else {
                right = mid
            }
        }
        low = left
    }

// 计算价值严格大于 low 的价值和，以及这些价值的个数
    for i, v := range value {
        if v > low {
            dec := decay[i]
            k := (v-low-1)/dec + 1
            m -= k
            ans += (v*2 - dec*(k-1)) * k
        }
    }
    ans /= 2       // 把除以 2 提到循环外面
    ans += m * low // 剩余 m 次选的价值都是 low
    return ans % 1_000_000_007
}

func main() {
    value := []int{6, 5, 4}
    decay := []int{2, 1, 1}
    m := 4
    result := maxTotalValue(value, decay, m)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def maxTotalValue(value, decay, m):
    def check(low):
        leftM = m
        for v, d in zip(value, decay):
            if v >= low:
                leftM -= (v - low) // d + 1
                if leftM < 0:
                    return True
        return False

low = 0
    if check(0):
        left, right = 0, max(value) + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        low = left

ans = 0
    for v, d in zip(value, decay):
        if v > low:
            k = (v - low - 1) // d + 1
            m -= k
            ans += (v * 2 - d * (k - 1)) * k

ans //= 2
    ans += m * low
    return ans % 1_000_000_007

if __name__ == "__main__":
    value = [6, 5, 4]
    decay = [2, 1, 1]
    m = 4
    print(maxTotalValue(value, decay, m)) 

C++完整代码如下：

  

  

  


using namespace std;

long long maxTotalValue(vector& value, vector& decay, int m) {
    auto check = [&](int low) -> bool {
        long long leftM = m;
        for (size_t i = 0; i < value.size(); ++i) {
            int v = value[i];
            int d = decay[i];
            if (v >= low) {
                leftM -= (v - low) / d + 1;
                if (leftM < 0) {
                    returntrue;
                }
            }
        }
        returnfalse;
    };

int low = 0;
    if (check(0)) {
        int left = 0;
        int right = *max_element(value.begin(), value.end()) + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        low = left;
    }

long long ans = 0;
    for (size_t i = 0; i < value.size(); ++i) {
        int v = value[i];
        int d = decay[i];
        if (v > low) {
            int k = (v - low - 1) / d + 1;
            m -= k;
            ans += ((long long)v * 2 - (long long)d * (k - 1)) * k;
        }
    }

ans /= 2;
    ans += (long long)m * low;
    return ans % 1000000007;
}

int main() {
    vector value = {6, 5, 4};
    vector decay = {2, 1, 1};
    int m = 4;

long long result = maxTotalValue(value, decay, m);
    cout << result << endl;  

return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。