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

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

packagemainimport("fmt""slices")funcmaxPoints(a,b[]int,kint)(ansint64){n:=len(a)d:=a[:0]fori,x:=rangea{ans+=int64(x)v:=b[i]-xifv>0{d=append(d,v)}}slices.SortFunc(d,func(a,bint)int{returnb-a})for_,x:=ranged[:min(n-k,len(d))]{ans+=int64(x)}return}funcmain(){technique1:=[]int{5,2,10}technique2:=[]int{10,3,8}k:=2result:=maxPoints(technique1,technique2,k)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defmax_points(a,b,k):ans=sum(a)n=len(a)d=[]forx,yinzip(a,b):v=y-xifv>0:d.append(v)d.sort(reverse=True)limit=min(n-k,len(d))foriinrange(limit):ans+=d[i]returnansdefmain():technique1=[5,2,10]technique2=[10,3,8]k=2result=max_points(technique1,technique2,k)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<numeric>usingnamespacestd;longlongmaxPoints(constvector<int>&a,constvector<int>&b,intk){longlongans=accumulate(a.begin(),a.end(),0LL);intn=a.size();vector<int>d;for(inti=0;i<n;i++){intv=b[i]-a[i];if(v>0){d.push_back(v);}}sort(d.begin(),d.end(),greater<int>());intlimit=min(n-k,(int)d.size());for(inti=0;i<limit;i++){ans+=d[i];}returnans;}intmain(){vector<int>technique1={5,2,10};vector<int>technique2={10,3,8};intk=2;longlongresult=maxPoints(technique1,technique2,k);cout<<result<<endl;return0;}