题解 | #两个有序数组间相加和的Topk问题#

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n1,n2,n3,k,sum = 0;
    cin>>n1>>k;
    vector<int> a(n1);
    for(int i = 0;i<n1;i++)
    {
        cin>>a[i];
    }
    n2 = n1;
    vector<int> b(n2);
    for(int i = 0;i<n2;i++)
    {
        cin>>b[i];
    }
    if(k>n1) n3 = n1;
    else n3 = k;
    vector<int> c(n3);
    vector<int> d(n3);
  //这里用c存所有可能最大的组合，i为a的下标，d[i]为b的下标
    for(int i = 0; i<n3;i++)
    {
        c[i] = a[n1-i-1]+b[n2-1];
        d[i] = n2-1;
    }
    for(int i = 0;i<k;i++)
    {
        int mix= c[0],mixd=0;
        for(int j = 1;j<n3;j++)
        {
            if(mix<c[j])
            {
                mix = c[j];
                mixd = j;
            }
        }
        cout<<mix<<" ";
	  //找到c中最大值，并通过b的下标减一更新c的值
        d[mixd]--;
        if(d[mixd]<0)
            c[mixd] = 0;
        else c[mixd] = c[mixd] - b[d[mixd]+1]+b[d[mixd]];
    }
}