题目链接：http://codeforces.com/contest/865/problem/B
题目：
It's another Start[c]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem), and all pizzas contain exactly S slices.
It is known that the i-th contestant will eat si slices of pizza, and gain ai happiness for each slice of type 1 pizza they eat, and bihappiness for each slice of type 2 pizza they eat. We can order any number of type 1 and type 2 pizzas, but we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices. Given that restriction, what is the maximum possible total happiness that can be achieved?
The first line of input will contain integers N and S (1 ≤ N ≤ 105, 1 ≤ S ≤ 105), the number of contestants and the number of slices per pizza, respectively. N lines follow.
The i-th such line contains integers si, ai, and bi (1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 105), the number of slices the i-th contestant will eat, the happiness they will gain from each type 1 slice they eat, and the happiness they will gain from each type 2 slice they eat, respectively.
Print the maximum total happiness that can be achieved.
3 12
3 5 7
4 6 7
5 9 5
84
6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6
314
In the first example, you only need to buy one pizza. If you buy a type 1 pizza, the total happiness will be 3·5 + 4·6 + 5·9 = 84, and if you buy a type 2 pizza, the total happiness will be 3·7 + 4·7 + 5·5 = 74.
题意：有N位选手参加比赛，主办方要预定披萨，现有A，B两种披萨，都有S块，每位选手要吃si块，并且吃A披萨得到的满意值为ai，吃B披萨得到的满意值为bi。求预定最少量的披萨（前提当然是每位选手都能吃到si块啦）得到的最大满意值为多少。
题解：先把最大满意值算出来，分别统计吃A披萨多少块，吃B披萨多少块，然后块数对S求余。我们假设A披萨余下t1，B披萨余下t2。
分情况讨论一下：
1.如果t1+t2>S，那么肯定要点两份，所以不用分来分去了，直接得到最大值。
2.如果t1+t2<=S，那么我们我们分两次考虑下，第一次把t1都分给B披萨，第二次把t2都分给A披萨，取最大值即可。
在分配披萨的过程中，因为我们已经拿到最大满意值了，要考虑的是减掉最少值，当然是满意值ai-bi接近0的情况最划算咯。
因为数据挺大的，我们可以二分下，找到最优位置。
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 6 typedef long long LL; 7 const int maxn=1e5+10; 8 struct TnT{ 9 LL s,a,b; 10 }T[maxn]; 11 LL TT[maxn]; 12 13 bool cmp1(TnT x,TnT y){ 14 return (x.a-x.b)<(y.a-y.b); 15 } 16 17 bool cmp2(TnT x,TnT y){ 18 return (x.b-x.a)<(y.b-y.a); 19 } 20 21 int main(){ 22 LL N,S,pos,cnt,t1=0,t2=0; 23 LL tmp,sum=0,ans=0; 24 scanf("%lld %lld",&N,&S); 25 for(LL i=0;i<N;i++){ 26 scanf("%lld %lld %lld",&T[i].s,&T[i].a,&T[i].b); 27 if(T[i].a>T[i].b) t1+=T[i].s,sum+=T[i].s*T[i].a; 28 else t2+=T[i].s,sum+=T[i].s*T[i].b; 29 } 30 t1=t1%S;t2=t2%S; 31 32 if(t1+t2>S) {cout<<sum<<endl;return 0;} //哇！这里超重要的！ 33 34 //cout<<"t1 = "<<t1<<" t2 = "<<t2<<endl; 35 sort(T,T+N,cmp1); 36 for(LL i=0;i<N;i++) TT[i]=T[i].a-T[i].b; 37 pos=upper_bound(TT,TT+N,0)-TT; 38 //cout<<"pos = "<<pos<<endl; 39 //cout<<"sum = "<<sum<<endl; 40 cnt=t1;tmp=sum; 41 for(LL i=pos;i<N;i++){ 42 if(cnt-T[i].s<=0){ 43 tmp-=cnt*TT[i]; 44 break; 45 } 46 else{ 47 tmp-=T[i].s*TT[i]; 48 cnt-=T[i].s; 49 } 50 } 51 ans=max(ans,tmp); 52 53 54 sort(T,T+N,cmp2); 55 for(LL i=0;i<N;i++) TT[i]=T[i].b-T[i].a; 56 pos=lower_bound(TT,TT+N,0)-TT; 57 cnt=t2;tmp=sum; 58 for(LL i=pos;i<N;i++){ 59 if(cnt-T[i].s<=0){ 60 tmp-=cnt*TT[i]; 61 break; 62 } 63 else{ 64 tmp-=T[i].s*TT[i]; 65 cnt-=T[i].s; 66 } 67 } 68 ans=max(ans,tmp); 69 printf("%lld\n",ans); 70 return 0; 71 }