C - Ordering Pizza CodeForces - 867C（贪心，好题！）

本文主要是介绍C - Ordering Pizza CodeForces - 867C（贪心，好题！），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 bi happiness 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?

Input
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.

Output
Print the maximum total happiness that can be achieved.

Examples
Input
3 12
3 5 7
4 6 7
5 9 5
Output
84
Input
6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6
Output
314
Note
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.

题意： 2种匹萨，每个人吃不同种类的匹萨有不同的欢乐值。匹萨可以分成很多块。但只能买整数个匹萨，问买刚好够的匹萨，使得欢乐值总和最高。

思路： 假设匹萨可以分开买，那就没有关系了，每个人吃最高换了值得那一份匹萨就可以了。关键这里匹萨是正数的，类似01背包和部分背包的区别，这就牵扯到用不完的问题了。

有两种解法，都是从不完整匹萨这个角度开始考虑的
1.先考虑每个人吃的匹萨的整数部分，这部分直接买就可以了，可以吃自己最喜欢的种类。剩下的部分加起来，如果加起来的部分大于一整个匹萨，就可以买两个，使得剩余部分都可以分配到最高的欢乐值。不然的话只能选一个匹萨，总有一种人的匹萨要改变，算出改变的值即可。
2.还有一种方法，每次只考虑单个匹萨，然后取这个匹萨能够产生的最大价值。两种方法本质上都是从整数上着手，去除确定答案的部分简化问题。

第一种方法

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;
typedef long long ll;
vector<pair<ll,ll> >s1;
vector<pair<ll,ll> >s2;int main()
{ll n,sum;scanf("%lld%lld",&n,&sum);ll ans = 0;ll sum1 = 0,sum2 = 0;for(ll i = 1;i <= n;i++){ll s,a,b;scanf("%lld%lld%lld",&s,&a,&b);if(a > b){ans += a * s;s1.push_back(make_pair(a - b,s));sum1 += s;}else{ans += b * s;s2.push_back(make_pair(b - a,s));sum2 += s;}}sum1 %= sum;sum2 %= sum;if(sum1 + sum2 > sum){printf("%lld\n",ans);}else{sort(s1.begin(),s1.end());sort(s2.begin(),s2.end());ll num1 = 0,num2 = 0;for(ll i = 0;i < s1.size();i++){num1 += min(s1[i].second,sum1) * s1[i].first;sum1 -= min(s1[i].second,sum1);}for(ll i = 0;i < s2.size();i++){num2 += min(s2[i].second,sum2) * s2[i].first;sum2 -= min(s2[i].second,sum2);}ans -= min(num1,num2);printf("%lld\n",ans);}return 0;
}

第二种方法

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;
typedef long long ll;
vector<pair<ll,ll> >S;int main()
{int n,sum;scanf("%d%d",&n,&sum);ll ans = 0;ll csum = 0;for(int i = 1;i <= n;i++){ll s,a,b;scanf("%lld%lld%lld",&s,&a,&b);ans += (ll)b * s;S.push_back(make_pair(a - b,s));csum += s;}if(csum % sum){S.push_back(make_pair(0,sum - csum % sum));}sort(S.begin(),S.end());ll ccnt = 0;csum = 0;for(int i = 0;i < S.size();i++){ll a = S[i].first, s = S[i].second;if(ccnt + s >= sum){//上一个整数匹萨的决策csum += a * (sum - ccnt);ans += max(csum,(ll)0);//当前整数部分匹萨的决策s -= (sum - ccnt);ans += (s / sum) * max(a * sum,(ll)0);//多余f匹萨留给下一步的决策ccnt = s % sum;csum = ccnt * a;}else{//非整数时候的决策，为凑成一个整数匹萨做准备。ccnt += s;csum += s * a;}}printf("%lld\n",ans);return 0;
}