题意:给定一个 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;
}

分类: 文章

0 条评论

发表评论

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