Main » 2013 September 25 » [NOIP2012模拟赛No.9]序列二
4:27 PM [NOIP2012模拟赛No.9]序列二 |
用堆来解(套个set)复杂度为O(mnlgn)#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #define N 100010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; struct node { int x,y; long long d; bool operator<(const node A)const { if (d<A.d) return 1; if (d>A.d) return 0; if (d==A.d) { if (x<A.x) return 1; return 0; } } }; multiset<node> S; long long a[N],ans[N],anst[N]; int main() { int n,m,i,j; scanf("%d %d",&m,&n); FOR(i,1,m) { S.clear(); FOR(j,1,n) scanf("%lld",&a[j]); sort(a+1,a+1+n); if (i==1) {FOR(j,1,n) ans[j]=a[j];continue;} node t; t.x=1;t.y=1;t.d=a[1]+ans[1]; S.insert(t); FOR(j,1,n) { set<node>::iterator it=S.begin(); node tt=*it; anst[j]=tt.d; S.erase(tt); node tt1=tt,tt2=tt; tt1.x++;tt2.y++; tt1.d=a[tt1.x]+ans[tt1.y]; tt2.d=a[tt2.x]+ans[tt2.y]; S.insert(tt1); S.insert(tt2); } memcpy(ans,anst,sizeof(ans)); } FOR(i,1,n-1) printf("%lld ",ans[i]); printf("%lld\n",ans[n]); } |
|
|
| Total comments: 0 | |