问个数组的题目

之前见过一个店面题 给两个长度一样的数字数组 问怎么取使得和最大

举个例子 数组A是[4,2,1] 数组B是[2,5,3] 如果规定只能在A里取2个数 那么最后的结果就是[4,1] 和[5] 总和就是10
数组A是[7,4,3] 数组B是[6,1,1] 只能在A里去两个数 那么最后的结果就是[4,3]和6 总和就是13

只能想到2^n的暴力解法 但是肯定不对 求问有没有什么更快的

刷题网1029 那题求最小，这题求最大，反着做就可以了

没太理解给的例子？为什么不能从A取最大的两个数？

wangs7 发表于 2019-5-15 06:00
没太理解给的例子？为什么不能从A取最大的两个数？

如果取了A[i] 那么B[i]就不能取了 第二个例子 如果从A取最大的两个数 那么总和就是12 不是最优解

补充内容 (2019-5-15 06:06):
如果取了A[i] 那么B[i]就不能取了

从楼主给的例子，这题意思是两个长度为N的数组A和B，允许从A中选K个数，从B中选N-K个数 (A[i],B[i]只能取一个？)。如果这样的话按A和B的差排序，前面K个选A，后面的N-K选B就行了？是不是我想简单了。。。

A=[4,2,1]
B=[2,5,3]

sort based on (A[i]-B[i],i) ->  ((2,0),(-2,2),(-3,1)

k = 2，答案就是A[0]+A[2]+B[1] =10

同意楼上，就按A-B 降序， 然后取K个A 后面N-K个B，复杂度nlogn。或者用maxheap 然后nlogk。