首页 > 其他 > 详细

P1392 取数[堆]

时间:2019-09-12 23:32:03      阅读:15      评论:0      收藏:0      [点我收藏+]

标签:con   ace   如果   node   pac   是我   

题目描述

在一个n行m列的数阵中,你须在每一行取一个数(共n个数),并将它们相加得到一个和。对于给定的数阵,请你输出和前k小的取数方法。

解析

写这题完全自闭。

根本没联想起远古时期做的 P1631 序列合并 ,这题几乎是我刚入门做的了,代码还是仿的。

真的想了很久,怀疑自己智商.jpg。


首先如果做了 P1631 序列合并 而且还记得,那么这道题其实很好做。实际上就是把求两行的前\(k\)小和改成了求\(n\)行的前\(k\)小和。

两行的情况:设单调递增数列\(a,b\),其存在最小值\(a_1+b_1\),次小值为\(min(a_2+b_1,a_1+b_2)\)

推广到一般,对于第\(k\)小值\(a_n+b_m\),我们有第\(k+1\)小值\(min(a_n+b_{m+1},a_{n+1}+b_m)\)

因此有算法,我们将\(a_1+b_1\)加入优先队列,不断扩展,每次可扩展出两个可行解,执行\(k\)次,所以显然也有最终答案下标一定不会超过\(k\)

\(n\)行的情况,我们在行与行间进行迭代,应用与两行情况类似的算法。

换句话说,对于递增的行\(x,y,z\),该算法就是先求\(x,y\)的前\(k\)小和,这些和组成新的数列,再跟\(z\)执行该算法,可以求出\(x,y,z\)三行的前\(k\)小和。


简单证明:

\(x,y\)的前\(k\)小和构成的数列为\(x'\)\(sum(i,j)\)表示从第\(i,j\)行分别任意取一个元素相加得到的新数列。如果\(z\)中有一元素\(q\),其与一元素\(p\in sum(x,y)\),且\(p \notin x'\)相加构成\(sum(x',z)\)的第\(k'\)小值,且\(k'<k\)。那么一定有一元素\(p' \in x'\)\(q\)构成更优的第\(k'\)小值,故这样的\(p\)不存在。即\(sum(x',z)=sum(x,y,z)\)。也就是说这个迭代是没有问题的。

参考代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define N 801
using namespace std;
inline int read()
{
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct node{
    int val,ap,bp;
    bool operator<(const node &a)const{
        return a.val<val;
    }
    node(){}
    node(int _v,int _a,int _b){val=_v,ap=_a,bp=_b;}
};
priority_queue<node> q;
int a[N],b[N],n,m,k,t[N];
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;++i) a[i]=read();
    sort(a+1,a+m+1);
    for(int i=2;i<=n;++i){
        for(int j=1;j<=m;++j) b[j]=read();
        sort(b+1,b+m+1);
        while(q.size()) q.pop();//换成开个新的优先队列或许更快?
        for(int j=1;j<=k;++j) q.push(node(a[j]+b[1],j,1));//小优化
        for(int j=1;j<=k;++j){
            node x=q.top();q.pop();
            t[j]=x.val;
            if(x.bp<m) q.push(node(a[x.ap]+b[x.bp+1],x.ap,x.bp+1));
        }
        memcpy(a,t,sizeof(a));//迭代
    }
    for(int i=1;i<=k;++i) printf("%d ",a[i]);
    return 0;
}

P1392 取数[堆]

标签:con   ace   如果   node   pac   是我   

原文:https://www.cnblogs.com/DarkValkyrie/p/11515461.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号