取数
题目描述
在一个n行m列的数阵中,你须在每一行取一个数(共n个数),并将它们相加得到一个和。对于给定的数阵,请你输出和前k小的取数方法。
输入输出格式
输入格式:
第一行,三个数n,m,k。
第2~n+1行,每行m个正整数
输出格式:
一行共k个数,代表在每一行取一个数前k小的加和
输入输出样例
说明
对于20%的数据,n≤8
对于100%的数据,n≤800,k≤m≤800
分析:
WA了无数次,最后发现就是一个取址符号没打。。。。。。真煞笔。。。
这个蒟蒻真的懒得写了,如果想看思路就参考一下这里吧,蒟蒻就只上代码了。
Code:
#include<bits/stdc++.h> using namespace std; int n,m,k,a[2][807]; int size,b[807],c,cc; struct Node{ int x,y,num; }bdg,h[50007]; inline void Swap(Node &x,Node &y) {Node temp=x;x=y;y=temp;} inline void ins(Node x) { h[++size]=x; int ka=size; while(ka>1){ if(h[ka].num<h[ka>>1].num){ Swap(h[ka],h[ka>>1]);ka>>=1;} else break;} } inline void delet() { h[1]=h[size--]; int ka=1,s=ka<<1; while(s<=size){ if(s<size&&h[s+1].num<h[s].num)s++; if(h[s].num<h[ka].num){ Swap(h[s],h[ka]);ka=s;s=ka<<1;} else break;} } inline Node get() { Node ret=h[1]; delet();return ret; } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) scanf("%d",&a[c][i]); sort(a[c]+1,a[c]+m+1); for(int j=2;j<=n;j++){ cc=1-c;size=0; for(int i=1;i<=m;i++) scanf("%d",&b[i]); sort(b+1,b+m+1); bdg.x=1; for(int i=1;i<=k;i++){ bdg.y=i;bdg.num=a[c][1]+b[i];ins(bdg);} for(int i=1;i<=k;i++){ bdg=get(); a[cc][i]=bdg.num; bdg.x++;bdg.num=a[c][bdg.x]+b[bdg.y]; ins(bdg);} c=1-c;} for(int i=1;i<=k;i++) printf("%d ",a[c][i]); return 0; }