发布日期：2026-04-29 04:07 点击次数：120
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
1
0
输入：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（收益
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):
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
#include
#include
#include
using namespace std;
long long maxPoints(const vector& a, const vector& b, int k) {
long long ans = accumulate(a.begin, a.end, 0LL);
int n = a.size;
vector d;
for (int i = 0; i
int v = b[i] - a[i];
if (v > 0) {
d.push_back(v);
}
}
sort(d.begin, d.end, greater);
int limit = min(n - k, (int)d.size);
for (int i = 0; i
ans += d[i];
}
return ans;
}
int main {
vector technique1 = {5, 2, 10};
vector technique2 = {10, 3, 8};
int k = 2;
long long result = maxPoints(technique1, technique2, k);
cout
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。