[loj3366]嘉年华奖券

联系绝对值的几何意义/分类讨论，不难发现若$n$张奖券上的数从小到大依次为$a_{i}$，则收益为$\sum_{i=1}^{\frac{n}{2}}a_{i+\frac{n}{2}}-a_{i}$

假设确定了这$nk$个数字，设这从小到大依次为$a_{i}$，容易发现答案最大不会超过$\sum_{i=1}^{\frac{nk}{2}}a_{i+\frac{nk}{2}}-a_{i}$；同时，如果存在$x>y$满足$a_{x}$为负号且$a_{y}$为正号，就交换$(a_{x},a_{y})$，最终一定可以取到最大值

再考虑如何确定这$nk$个数字，先取出每一个组中最小的数，符号都为负，然后贪心$\frac{nk}{2}$次选择一组将符号为负且最大（原值）的数替换为未被选择的最大的数，使得收益（即两数之和）最大，并用set维护即可

还有构造方案的问题，由于前者已经证明了必然存在方案，那么随便构造一轮后，这个子问题类似的依然可以证明存在方案，因此每一轮可以任意构造，先优先考虑全是正号/负号的组，其余组再任意选择即可

 1 #include "tickets.h"

 2 #include<bits/stdc++.h>

 3 using namespace std;

 4 #define N 1505

 5 vector<vector<int> >a;

 6 priority_queue<pair<int,int> >q;

 7 int n,m,mn[N],mx[N],p[N];

 8 long long find_maximum(int k,vector<vector<int> >c){

 9     a=c;

10     n=a.size();

11     m=a[0].size();

12     for(int i=0;i<n;i++){

13         a[i].push_back(0);

14         for(int j=m;j;j--)a[i][j]=a[i][j-1];

15         a[i][0]=0;

16     }

17     for(int i=0;i<n;i++){

18         mn[i]=k;

19         q.push(make_pair(a[i][mn[i]]+a[i][m],i));

20     }

21     for(int i=0;i<n*k/2;i++){

22         int x=q.top().second;

23         q.pop();

24         mn[x]--;

25         mx[x]++;

26         if (mn[x])q.push(make_pair(a[x][mn[x]]+a[x][m-mx[x]],x));

27     }

28     long long ans=0;

29     for(int i=0;i<n;i++){

30         for(int j=1;j<=mn[i];j++)ans-=a[i][j];

31         for(int j=m-mx[i]+1;j<=m;j++)ans+=a[i][j];

32     }

33     for(int i=0;i<n;i++){

34         a[i].pop_back();

35         for(int j=mn[i];j<m-mx[i];j++)a[i][j]=-1;

36     }

37     for(int i=0;i<k;i++){

38         int x=0,y=0;

39         memset(p,-1,sizeof(p));

40         for(int j=0;j<n;j++){

41             if (!mn[j])p[j]=0;

42             if (!mx[j])p[j]=1;

43             if ((mn[j])&&(mx[j]))y++;

44             else x+=2*p[j]-1;

45         }

46         y=(x+y)/2;

47         for(int j=0;j<n;j++)

48             if ((mn[j])&&(mx[j])){

49                 p[j]=(y<=0);

50                 y--;

51             }

52         for(int j=0;j<n;j++)

53             if (p[j])a[j][--mn[j]]=i;

54             else a[j][m-mx[j]--]=i;

55     }

56     allocate_tickets(a);

57     return ans;

58 }

巴特西

[loj3366]嘉年华奖券

最新文章

热门文章