2026-04-18：选择 K 个任务的最大总分数。用go语言，给定两个长度为 n 的整数数组 A 和 B，表示 n 个任务分别用两种技巧完成时的得分。

福大大架构师每日一题

发布于 2026-04-21 14:00:04

510

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-04-18：选择 K 个任务的最大总分数。用go语言，给定两个长度为 n 的整数数组 A 和 B，表示 n 个任务分别用两种技巧完成时的得分。

第 i 个任务：

• 选择技巧 1，可得 A[i] 分
• 选择技巧 2，可得 B[i] 分

再给定整数 k，要求你至少要有 k 个任务使用技巧 1 完成（这 k 个任务不要求是连续的或前面的任意位置）。其余任务可以任意选择技巧 1 或技巧 2。

目标是：在满足“技巧 1 的任务数不少于 k”的前提下，选择每个任务使用哪种技巧，使总得分尽可能大。

输出这个最大可能的总分数。

1 <= n == technique1.length == technique2.length <= 100000。

1 <= technique1[i], technique2[i] <= 100000。

0 <= k <= n。

输入：technique1 = [5,2,10], technique2 = [10,3,8], k = 2。

输出：22。

解释：

我们必须使用 technique1 完成至少 k = 2 个任务。

选择 technique1[1] 和 technique1[2]（使用技巧 1 完成），以及 technique2[0]（使用技巧 2 完成），可以获得最大分数：2 + 10 + 10 = 22。

题目来自力扣3767。

算法执行步骤详细解析（结合题目与示例）

第一步：基础分数初始化（全选技巧1）

1. 规则：题目要求至少k个任务用技巧1，最基础的方案是所有任务都用技巧1，先计算这个基础总分。
2. 计算： A数组所有元素求和：5 + 2 + 10 = 17
3. 此时满足约束：3个任务都用技巧1，远大于k=2的要求。

第二步：计算「替换收益」，筛选正向收益

核心思路：在保证至少k个任务用技巧1的前提下，把部分任务从技巧1换成技巧2，如果替换后分数变高，就替换。

1. 定义收益：第i个任务，收益 = B[i]（技巧2分数） - A[i]（技巧1分数）
- • 收益>0：换成技巧2，总分会增加
- • 收益≤0：换成技巧2，总分不变/减少，不替换
2. 逐个计算收益：
- • 任务0：10-5=5（收益>0，记录）
- • 任务1：3-2=1（收益>0，记录）
- • 任务2：8-10=-2（收益<0，不记录）
3. 得到正向收益列表：[5, 1]

第三步：确定最多能替换的任务数量

约束：必须保留至少k个任务用技巧1，总任务数n=3。

1. 最多可替换数量 = 总任务数 - 必须保留的技巧1任务数 = n - k = 3-2 = 1个
2. 含义：我们最多只能把1个任务从技巧1换成技巧2，剩下2个必须用技巧1。

第四步：优先选择收益最高的替换（贪心策略）

1. 对正向收益列表从大到小排序：[5, 1] 排序后还是 [5, 1]
2. 选取前「最多可替换数量」个收益（即前1个）：收益5
3. 把这个收益加到基础总分上：17 + 5 = 22

第五步：得到最终结果

最终最大总分数为22，和题目示例答案一致。

通用完整流程（适用于所有输入）

1. 基础总分计算 遍历数组A，累加所有元素得到基础总分（默认所有任务用技巧1，满足约束）。
2. 生成正向收益列表 遍历每个任务，计算B[i]-A[i]，只保留大于0的收益（只有替换能加分的才考虑）。
3. 排序收益 将正向收益列表从大到小降序排序（贪心：优先替换收益最高的任务）。
4. 计算可替换上限 最多能替换的任务数 = 总任务数n - 最少需要的技巧1任务数k。
5. 累加最优收益 取排序后收益列表中，前「可替换上限」个收益，全部加到基础总分上。
6. 输出结果 最终的和就是满足约束的最大总分数。

复杂度分析

1. 时间复杂度

• 遍历数组计算基础总分、生成收益列表：O(n)
• 对收益列表排序：收益列表长度最大为n，排序时间O(n log n)
• 遍历收益列表累加：O(n)
• 总时间复杂度：O(n log n) （这是处理n≤10⁵规模数据的最优解法之一）

2. 额外空间复杂度

• 仅创建了一个存储正向收益的切片，最大长度为n
• 无其他递归/大型数据结构
• 总额外空间复杂度：O(n)

总结

1. 核心逻辑：基础分（全技巧1）+ 最优替换收益，用贪心保证分数最大化；
2. 严格满足「至少k个技巧1」的约束；
3. 时间复杂度O(n log n)，空间复杂度O(n)，适配题目10万级数据规模。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func maxPoints(a, b []int, k int) (ans int64) {
    n := len(a)
    d := a[:0]
    for i, x := range a {
        ans += int64(x)
        v := b[i] - x
        if v > 0 {
            d = append(d, v)
        }
    }

    slices.SortFunc(d, func(a, b int)int { return b - a })
    for _, x := range d[:min(n-k, len(d))] {
        ans += int64(x)
    }
    return
}

func main() {
    technique1 := []int{5, 2, 10}
    technique2 := []int{10, 3, 8}
    k := 2
    result := maxPoints(technique1, technique2, k)
    fmt.Println(result)
}

Python完整代码如下：

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

def max_points(a, b, k):
    ans = sum(a)
    n = len(a)
    d = []
    
    for x, y in zip(a, b):
        v = y - x
        if v > 0:
            d.append(v)
    
    d.sort(reverse=True)
    limit = min(n - k, len(d))
    
    for i in range(limit):
        ans += d[i]
    
    return ans


def main():
    technique1 = [5, 2, 10]
    technique2 = [10, 3, 8]
    k = 2
    result = max_points(technique1, technique2, k)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

long long maxPoints(const vector<int>& a, const vector<int>& b, int k) {
    long long ans = accumulate(a.begin(), a.end(), 0LL);
    int n = a.size();
    vector<int> d;

    for (int i = 0; i < n; i++) {
        int v = b[i] - a[i];
        if (v > 0) {
            d.push_back(v);
        }
    }

    sort(d.begin(), d.end(), greater<int>());

    int limit = min(n - k, (int)d.size());
    for (int i = 0; i < limit; i++) {
        ans += d[i];
    }

    return ans;
}

int main() {
    vector<int> technique1 = {5, 2, 10};
    vector<int> technique2 = {10, 3, 8};
    int k = 2;

    long long result = maxPoints(technique1, technique2, k);
    cout << result << endl;

    return0;
}