路上的球

Description

There are two parallel roads, each containing N and M buckets, respectively. Each bucket may contain some balls. The buckets on both roads are kept in such a way that they are sorted according to the number of balls in them. Geek starts from the end of the road which has the bucket with a lower number of balls(i.e. if buckets are sorted in increasing order, then geek will start from the left side of the road). The geek can change the road only at the point of intersection(which means, buckets with the same number of balls on two roads). Now you need to help Geek to collect the maximum number of balls.

Input

The first line of input contains T denoting the number of test cases. The first line of each test case contains two integers N and M, denoting the number of buckets on road1 and road2 respectively. 2nd line of each test case contains N integers, number of balls in buckets on the first road. 3rd line of each test case contains M integers, number of balls in buckets on the second road.

Constraints:1<= T <= 1000，1<= N <= 10^3，1<= M <=10^3，0<= A[i],B[i]<=10^6

Output

For each test case output a single line containing the maximum possible balls that Geek can collect.

Sample Input

1
5 5
1    4 5 6 8
2 3 4    6 9

Sample Output

29

思路

把数组的位置调整一下看：

1 4 5 6 8
2 3 4 6 9

两条路在4的位置交叉，在6的位置交叉，两个数组被分为3段，能收集的最大值是三段中两条路的最大值。

max(1+4, 2+3+4) + max(5+6, 6) + max(8, 9) = 29

代码实现就简单了，

1. 首先找出两个数组中共同有的数common
2. 用common中的数把两个数组分割成若干个子数组
3. 累加每段两个数组对应子数组中和最大的一个

python

def solve(balls1, balls2):
    common = set(balls1) & set(balls2)
    arr1, arr2 = [], []
    for num in sorted(common):
        idx1 = balls1.index(num)
        idx2 = balls2.index(num)
        arr1.append(sum(balls1[:idx1+1]))
        arr2.append(sum(balls2[:idx2+1]))
        balls1 = balls1[idx1+1:]
        balls2 = balls2[idx2+1:]
    ans = max(sum(balls1), sum(balls2))
    for val1, val2 in zip(arr1, arr2):
        ans += max(val1, val2)
    return ans
    
for _ in range(int(input())):
    input()
    balls1 = list(map(int, input().split()))
    balls2 = list(map(int, input().split()))
    print(solve(balls1, balls2))