2017 ECJTU ACM 程序设计竞赛

时间：2023-03-09 13:03:55
2017 ECJTU ACM 程序设计竞赛

大厦

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 25   Accepted Submission(s) : 7

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

给你一个n(1<=n<=1000)层楼的大厦，每一楼里面有m(1<=m<=1000)房间，
每个房间一定的金钱X(1<=x<=1000)，假设不同楼层的房间是互通的，相同楼层的房间是不互通的。也就是说每层只能取一个，现在给你一个捡钱的机会。捡钱的方式不同，会导致你得到的钱的不同，求可能捡到的钱的前k大的和

Input

输入一个T，表示T组样例；
每组数据第一行输入n，m，k
接下来输入n行，每行m个数，代表这个房间拥有的金钱

Output

输出可能捡到的钱的前k大的和

Sample Input

1

3 4 5

1 2 3 4

5 6 7 8

1 2 3 4

Sample Output

75

题解

假设任意两层为集合A B(从大到小排序）对于B集合的元素B[i]，显然它和A[1]组合值最大，
如果B[i]+A[j]是前K大值中的一个，那么B[i]+A[k](1<=k < j)必然也是前K大的，
所以B[i]+A[j]被选则B[i]+A[j-1]之前就被选了，
所以优先队列中只需维护Size(B)个元素，首先把A[1]+B[i]全部进队，
每次从队首拿出一个组合(i,j)(表示A[i]+B[j])，把A[i+1]+B[j]进队，
直到拿出K个元素为止，即为这两个集合合并的前K大
n层的话只要把每次得到的结果和其他层按照这样处理就可以了

AC代码
 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <sstream>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <vector>

 using namespace std;

 const int maxn= ;

 const double eps= 1e-;

 const int inf = 0x3f3f3f3f;

 typedef long long ll;

 int k,n,m;

 vector<int> a[maxn];

 vector<int> ans,d;

 int cmp(int a,int b)

 {

     return a>b;

 }

 struct node

 {

     int i,j,val;

     node(){}

     node(int i,int j,int val):i(i),j(j),val(val){}

     bool operator <(const node &a)const

     {

         return val<a.val;

     }

 };

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

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

         int x;

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

             a[i].clear();

         ans.clear();

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

         {

             for(int j=;j<=m;j++)

             {

                 scanf("%d",&x);

                 a[i].push_back(x);

             }

             sort(a[i].begin(),a[i].end(),cmp);

         }

         priority_queue<node> q;

         ans.push_back();

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

         {

             int x,y,z;

             for(int j=;j<m;j++)

             {

                 z=a[i][j]+ans[];

                 q.push(node(,j,z));

             }

             while(d.size()<k&&!q.empty())

             {

                 node e=q.top();q.pop();

                 d.push_back(e.val);

                //printf("%d %d\n",cnt,d[cnt]);

                 //cnt++;

                 if(e.i+<k&&i!=)

                     q.push(node(e.i+,e.j,ans[e.i+]+a[i][e.j]));

             }

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

             ans.assign(d.begin(),d.end());

             d.clear();

         }

         ll sum=;

         for(int i=;i<k;i++)

             sum+=ans[i];

         printf("%lld\n",sum);

     }

 }

相关文章