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规则题目要求至少k个任务用技巧1最基础的方案是所有任务都用技巧1先计算这个基础总分。计算A数组所有元素求和5 2 10 17此时满足约束3个任务都用技巧1远大于k2的要求。第二步计算「替换收益」筛选正向收益核心思路在保证至少k个任务用技巧1的前提下把部分任务从技巧1换成技巧2如果替换后分数变高就替换。定义收益第i个任务收益 B[i]技巧2分数 - A[i]技巧1分数收益0换成技巧2总分会增加收益≤0换成技巧2总分不变/减少不替换逐个计算收益任务010-55收益0记录任务13-21收益0记录任务28-10-2收益0不记录得到正向收益列表[5, 1]第三步确定最多能替换的任务数量约束必须保留至少k个任务用技巧1总任务数n3。最多可替换数量 总任务数 - 必须保留的技巧1任务数 n - k 3-2 1个含义我们最多只能把1个任务从技巧1换成技巧2剩下2个必须用技巧1。第四步优先选择收益最高的替换贪心策略对正向收益列表从大到小排序[5, 1]排序后还是[5, 1]选取前「最多可替换数量」个收益即前1个收益5把这个收益加到基础总分上17 5 22第五步得到最终结果最终最大总分数为22和题目示例答案一致。通用完整流程适用于所有输入基础总分计算遍历数组A累加所有元素得到基础总分默认所有任务用技巧1满足约束。生成正向收益列表遍历每个任务计算B[i]-A[i]只保留大于0的收益只有替换能加分的才考虑。排序收益将正向收益列表从大到小降序排序贪心优先替换收益最高的任务。计算可替换上限最多能替换的任务数 总任务数n - 最少需要的技巧1任务数k。累加最优收益取排序后收益列表中前「可替换上限」个收益全部加到基础总分上。输出结果最终的和就是满足约束的最大总分数。复杂度分析1. 时间复杂度遍历数组计算基础总分、生成收益列表O(n)对收益列表排序收益列表长度最大为n排序时间O(n log n)遍历收益列表累加O(n)总时间复杂度O(n log n)这是处理n≤10⁵规模数据的最优解法之一2. 额外空间复杂度仅创建了一个存储正向收益的切片最大长度为n无其他递归/大型数据结构总额外空间复杂度O(n)总结核心逻辑基础分全技巧1 最优替换收益用贪心保证分数最大化严格满足「至少k个技巧1」的约束时间复杂度O(n log n)空间复杂度O(n)适配题目10万级数据规模。Go完整代码如下packagemainimport(fmtslices)funcmaxPoints(a,b[]int,kint)(ansint64){n:len(a)d:a[:0]fori,x:rangea{ansint64(x)v:b[i]-xifv0{dappend(d,v)}}slices.SortFunc(d,func(a,bint)int{returnb-a})for_,x:ranged[:min(n-k,len(d))]{ansint64(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):anssum(a)nlen(a)d[]forx,yinzip(a,b):vy-xifv0:d.append(v)d.sort(reverseTrue)limitmin(n-k,len(d))foriinrange(limit):ansd[i]returnansdefmain():technique1[5,2,10]technique2[10,3,8]k2resultmax_points(technique1,technique2,k)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includealgorithm#includenumericusingnamespacestd;longlongmaxPoints(constvectorinta,constvectorintb,intk){longlongansaccumulate(a.begin(),a.end(),0LL);intna.size();vectorintd;for(inti0;in;i){intvb[i]-a[i];if(v0){d.push_back(v);}}sort(d.begin(),d.end(),greaterint());intlimitmin(n-k,(int)d.size());for(inti0;ilimit;i){ansd[i];}returnans;}intmain(){vectorinttechnique1{5,2,10};vectorinttechnique2{10,3,8};intk2;longlongresultmaxPoints(technique1,technique2,k);coutresultendl;return0;}