Sequence

时间:2021-12-28 15:35:48

http://poj.org/problem?id=2442

用STL写的时间为:5657MS

 #include<cstdio>
#include<algorithm>
#include<queue>
#define MAXN 2005
using namespace std;
int main()
{
int t,n,m,c;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
int a[MAXN];
priority_queue< int,vector<int>,greater<int> >q;
priority_queue< int,vector<int>,less<int> >p;
for(int i=; i<m; i++)
{
scanf("%d",&c);
q.push(c);
}
for(int j=; j<n; j++)
{
for(int k=; k<m; k++)
{
scanf("%d",&a[k]);
}
while(!q.empty())
{
int mm=q.top();
q.pop();
for(int h=; h<m; h++)
{
if(p.size()==m&&p.top()>mm+a[h])
{
p.pop();
p.push(mm+a[h]);
}
else if(p.size()<m)
{
p.push(mm+a[h]);
}
}
}
while(!p.empty())
{
q.push(p.top());
p.pop();
}
}
int mark=;
for(int i=;i<m;i++)
{
if(mark)
{
printf("%d",q.top());
mark=;
}
else printf(" %d",q.top());
q.pop();
}
printf("\n");
}
return ;
}

我用堆写的时间:3969MS

 #include<cstdio>
#include<algorithm>
#include<queue>
#define MAXN 2005
long long a[],b[];
using namespace std;
int len=,len1=;
void up1(int n)
{
a[++len]=n;
int p=len;
int q=p/;
long long m=a[p];
while(q>=&&m<a[q])
{
a[p]=a[q];
p=q;
q=p/;
}
a[p]=m;
}
void up2(int n)
{
b[++len1]=n;
int p=len1;
int q=p/;
long long m=b[p];
while(q>=&&m>b[q])
{
b[p]=b[q];
p=q;
q=p/;
}
b[p]=m;
}
void down1(int p)
{
a[]=a[len--];
int q=p*;
long long m=a[p];
while(q<=len)
{
if(q<len&&a[q]>a[q+])
q++;
if(a[q]>=m) break;
else
{
a[p]=a[q];
p=q;
q=p*;
}
}
a[p]=m;
}
int pop1()
{
long long r=a[];
return r;
}
int pop2()
{
long long r=b[];
return r;
}
void down2(int p)
{
b[]=b[len1--];
int q=p*;
long long m=b[p];
while(q<=len1)
{
if(q<len1&&b[q]<b[q+])
q++;
if(b[q]<=m) break;
else
{
b[p]=b[q];
p=q;
q=p*;
}
}
b[p]=m;
} int main()
{
int t,n,m,c;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
int aa[MAXN];
for(int i=; i<m; i++)
{
scanf("%d",&c);
up1(c);
}
for(int j=; j<n; j++)
{
for(int k=; k<m; k++)
{
scanf("%d",&aa[k]);
}
while(len!=)
{
int mm=pop1();
down1();
for(int h=; h<m; h++)
{
if(len1>=m&&b[]>mm+aa[h])
{
down2();
up2(mm+aa[h]);
}
else if(len1<m)
{
up2(mm+aa[h]);
}
}
}
while(len1!=)
{
up1(b[]);
down2();
}
}
int mark=;
for(int i=;i<m;i++)
{
if(mark)
{
printf("%lld",a[]);
mark=;
}
else printf(" %lld",a[]);
down1();
}
printf("\n");
}
return ;
}