Sequence POJ

口胡一个结论：就是前i行产生的最小的n个和，一定可以在"前i-1行产生的最小n个和，每一个加上这一行的任意一个数，产生的n²个数"中找到。（其实显然是对的）

因此每次只需要求两个有n个数的序列每个序列中选一个产生的所有和中最小n个。方法就是先将两个序列排序，这之后去模拟一个一个取出和的过程。如果第一个序列取的已经确定，那么第二个序列一定是按顺序取。因此枚举第一个序列中取某一个，对于第一个序列中取某一个的情况维护当前已经取到的第二个序列中的序号。用优先队列维护最小的和，每次取出一个放进当前答案的数组，并将该和对应的第一个序列取法对应的第二个序列的序号加一并放回优先队列。

错误原因：

1.44行写成t[i]，会被只有一行的数据卡掉

2.求两行合并的时候用了n²算法，太暴力

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef int LL;

 typedef pair<LL,LL> P;

 typedef pair<LL,P> P2;

 priority_queue<P2,vector<P2>,greater<P2> > qq;

 LL a[][];

 LL t[];

 LL T,sum,m,n;

 int main()

 {

     P2 x;

     LL i,j;

     scanf("%d",&T);

     while(T--)

     {

         memset(a,,sizeof(a));

         memset(t,,sizeof(t));

         scanf("%d%d",&m,&n);

         for(i=;i<=m;i++)

         {

             for(j=;j<=n;j++)

                 scanf("%d",&a[i][j]);

             sort(a[i]+,a[i]+n+);

         }

         for(i=;i<=m;i++)

         {

             while(!qq.empty())    qq.pop();

             for(j=;j<=n;j++)

                 qq.push(P2(a[i-][j]+a[i][],P(j,)));

             for(j=;j<=n;j++)

             {

                 x=qq.top();

                 qq.pop();

                 t[j]=x.first;

                 qq.push(P2(a[i-][x.second.first]+a[i][x.second.second+],P(x.second.first,x.second.second+)));

             }

             memcpy(a[i],t,sizeof(t));

         }

         for(i=;i<=n;i++)

             printf("%d ",a[m][i]);

         puts("");

     }

     return ;

 }

巴特西

Sequence POJ - 2442

最新文章

热门文章