UVA11997 K Smallest Sums

简练一哈问题就是：给两个长度为 N $N$的数组 a $a$和 b $b$，求那么 a[i]+b[i] $a\left[i\right]+b\left[i\right]$有 N2 $N^2$种组合，求最小的前 N $N$个组合

比如 N=4 $N=4$
a:1,2,3,4 $a:1,2,3,4$
b:5,6,7,8 $b:5,6,7,8$
前 N $N$个最小的就是 6,7,7,8 $6,7,7,8$
数组都先排序哈

我们先弄个初始答案：什么叫初始答案喃？
比如 a $a$里面的每个数 a[i] $a\left[i\right]$都加上 b $b$数组里面最小的 b[1] $b\left[1\right]$，是不是差不多就是最小的 N $N$个数了
这 N $N$个数就是 6,7,8,9 $6,7,8,9$对吧
但是这里面还有点问题
最小的数是6没问题，但是第二小的数有两种组合都是： a[2]+b[1] $a\left[2\right]+b\left[1\right]$和 a[1]+b[2] $a\left[1\right]+b\left[2\right]$，那么这个 a[1]+b[2] $a\left[1\right]+b\left[2\right]$应该作为第三小才对，而这个第三小却没有算到，怎么办喃？

我们将我们的初始答案先弄到优先队列里面去，小的在队首，队首的就是最小的组合，而且这个最小的要用来优化，比如当前最小的是 a[1]+b[1] $a\left[1\right]+b\left[1\right]$，那么把 b[1] $b\left[1\right]$用 b[2] $b\left[2\right]$换掉，也是比较小的组合，那就把这种组合加进队列，与其他的比较，反正每次最小的都是队首的~

/* 给两个长度为N的数组a和b，求那么a[i]+b[i]有N^2种组合， 求最小的前N个组合 */
#include"iostream"
#include"algorithm"
#include"queue"
using namespace std;
const int maxn=1e6+5;
int a[maxn],b[maxn],c[maxn];
int N;
struct AAA
{
    int v,id;
    AAA (){}
    AAA (int v,int id):v(v),id(id){}
    bool operator<(const AAA &a)const
    {
        return a.v<v;
    }
};
int main()
{
    while(cin>>N)
    {
        priority_queue<AAA>que;
        for(int i=1;i<=N;i++)cin>>a[i];
        for(int i=1;i<=N;i++)cin>>b[i];
        sort(a+1,a+1+N);
        sort(b+1,b+1+N);
        for(int i=1;i<=N;i++)que.push(AAA(b[1]+a[i],1));
        for(int i=1;i<=N;i++)
        {
            AAA t=que.top();
            que.pop();
            c[i]=t.v;
            t.v=t.v-b[t.id]+b[t.id+1];
            t.id++;
            que.push(t);
        }
        for(int i=1;i<=N;i++)cout<<c[i]<<" ";
        cout<<endl;
    }
}

而这道题就是重复几次这样的操作就完了

#include"iostream"
#include"cstdio"
#include"algorithm"
#include"queue"
using namespace std;
const int maxn=750+5;
long long a[maxn],b[maxn];
long long N;
struct AAA
{
    long long v,id;
    AAA (){}
    AAA (long long v,long long id):v(v),id(id){}
    bool operator<(const AAA &a)const
    {
        return a.v<v;
    }
};
int f()
{
        priority_queue<AAA>que;
        for(int i=1;i<=N;i++)
        {
            que.push(AAA(b[1]+a[i],1));
        }
        for(int i=1;i<=N;i++)
        {
            AAA t=que.top();
            que.pop();
            a[i]=t.v;
            t.v=t.v-b[t.id]+b[t.id+1];
            t.id++;
            que.push(t);
        }
}
int main()
{

    while(cin>>N)
    {
        int T=N-1;
        for(int i=1;i<=N;i++)cin>>a[i];
        sort(a+1,a+1+N);
        while(T--)
        {
            for(int i=1;i<=N;i++)cin>>b[i];
            sort(b+1,b+1+N);
            f();
        }
        for(int i=1;i<N;i++)cout<<a[i]<<" ";
        cout<<a[N]<<endl;
    }

}