题意:给定一个k*k的矩阵,要求你每行选一个数,把他们相加得到kk个和。输出最小的k个和。(k<=750,多组数据)

分析:

首先我们从一个简单的问题入手。如果只有2行,每行k个数,最小的k个和怎么求?

先将这两行的数字升序排序,设第一行为数组A,第二行为B,构成前k小的数对的集合为W,可能成为前k小的数对的集合为P,没有使用过的数对的集合为Q,(注意PQ一定互为补集,所以程序中要确保这一点,防止数对重复取出)那么一开始,W={}, P={(A1,B1)}, Q=U-P.第一轮:由于P中唯一的数对为绝对最小的数对且W未满,所以将P中最小的数对取出放入W中。将Q中的(A1,B2)及(A2,B1)取出放入P中。第二轮:将P中最小的数对(Ai,Bi)取出,放入W中,Q中的(A[i+1],Bi)、(Ai,B[i+1])若存在,则放入P中。以此类推。

但是完全没有这么麻烦。

由于A和B的单调性,对于任意的Ai,(A[i]+B[j])也是存在单调性的。所以上面的问题可以转化为将k个数组

{A1+B1,A1+B2,A1+B3…}

{A2+B1,A2+B2,A2+B3…}

{A3+B1,A3+B2,A3+B3…}

{Ak+B1,Ak+B2,Ak+B3…} 归并为一个递增序列并取前k项。

所以相比于上一个方法,W P Q这几个集合仍然代表相同的意思,但是转移的方式变简单了:将P中最小的数对(Ai,Bi)取出,放入W;将(Ai,Bi)所在的数组(就是那k个中的一个)中的下一个(Ai,Bi+1)放入P,重复k次完成归并。

从理论到实际,也就是P集合用优先队列代替,模拟上述归并过程,时间复杂度O(k2·log2k)

现在再将两个数组的情况推广到k个数组。仅仅一步之遥。将所有的数组按照上述方法归并(k-1)次就是答案数组。

#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

int ar[1000][1000],ans[1000];

struct node
{
    int a,b,n;
    bool operator < (const node &ths)const{
        return n>ths.n;
    }
};

void ad(int *tar,int *a,int *b,int k)
{
    priority_queue<node> p;
    node tmp,now;
    for(int i=1;i<=k;i++)ans[i]=0;
    for(int i=1;i<=k;i++)
    {
        tmp.a=i,tmp.b=1,tmp.n=a[i]+b[1];
        p.push(tmp);
    }
    for(int i=1;i<=k;i++)
    {
        now=p.top();
        ans[i]=now.n,tmp.a=now.a,tmp.b=now.b+1,tmp.n=a[tmp.a]+b[tmp.b];
        p.pop(),p.push(tmp);
    }
    for(int i=1;i<=k;i++)tar[i]=ans[i];
}

int main()
{
    int k;
    while((scanf("%d",&k))!=EOF)
    {
        for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)scanf("%d",&ar[i][j]);
        for(int i=1;i<=k;i++)sort(ar[i]+1,ar[i]+k+1);
        for(int i=2;i<=k;i++)ad(ar[1],ar[1],ar[i],k);
        for(int i=1;i<=k;i++)if(i==1)printf("%d",ar[1][i]);else printf(" %d",ar[1][i]);
        printf("\n");
    }
    return 0;
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *