Codeforces Round #437 C. Ordering Pizza

题意: n个人吃披萨,总共有两种披萨,每种披萨都是有S块,给出每个人要吃的块数,吃第一种披萨能获得的happy值,吃第二种披萨能获得的happy值,问你,在购买的披萨数最少的情况下能获得的最大的总的happy值是多少(披萨可以买任意多个,吃不完也行 2333333)

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

思路:首先肯定是每个人都吃happy值更大的那一种披萨最优,但是有一个问题,可能会多出一点零头,那么我们记为sum1和sum2。
   如果sum1+sum2>S,那么这些零头肯定是要买两个披萨的,不如就各买各的,那么答案就是ans;
   但是如果sum1+sum2<=S,那么就要一起买一个披萨了,这样的话就用ans-min(让买第一种披萨的去买第二种的差值,
   让买第二种披萨的去买第一种的差值),
    这样算出来的结果就是答案了。
   (用结构体保存一下a,b,差值,然后按差值从小到大来排序,肯定是让差值小的最后买这样才最划算,因为如果要买另外一
    个这样损失最小)
   for(int i=0;i<n1;i++){
            ans1+=min(sum1,t1[i].s)*t1[i].c;
            sum1-=min(sum1,t1[i].s);
        }
    for(int i=0;i<n2;i++){
            ans2+=min(sum2,t2[i].s)*t2[i].c;
            sum2-=min(sum2,t2[i].s);
        }
    这两句话很关键是从一个帖子看到的23333。 代码: #include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e5+5; struct node{
    long long s,a,b,c;
}t1[maxn],t2[maxn];
bool cmp(node x,node y){
    return x.c<y.c;
} int main(){
    long long n,S,n1=0,n2=0,sum1=0,sum2=0,ans=0,ans1=0,ans2=0,x,y,z;
    cin>>n>>S;
    for(int i=0;i<n;i++){
        cin>>x>>y>>z;
        if(y>z){
            t1[n1].s=x;
            t1[n1].a=y;
            t1[n1].b=z;
            t1[n1].c=y-z;
            ans+=t1[n1].a*t1[n1].s;
            sum1=(sum1+t1[n1].s)%S;
            n1++;
        }
        else {
            t2[n2].s=x;
            t2[n2].a=y;
            t2[n2].b=z;
            t2[n2].c=z-y;
            ans+=t2[n2].b*t2[n2].s;
            sum2=(sum2+t2[n2].s)%S;
            n2++;
        }
    }
    if(sum1+sum2>S){
        cout<<ans<<endl;
    }
    else {
        sort(t1,t1+n1,cmp);
        for(int i=0;i<n1;i++){
            ans1+=min(sum1,t1[i].s)*t1[i].c;
            sum1-=min(sum1,t1[i].s);
        }
        sort(t2,t2+n2,cmp);
        for(int i=0;i<n2;i++){
            ans2+=min(sum2,t2[i].s)*t2[i].c;
            sum2-=min(sum2,t2[i].s);
        }
        if(ans1<ans2)ans-=ans1;
        else ans-=ans2;
        cout<<ans<<endl;
    }
    return 0;
}
上一篇:JavaScript中的this陷阱的最全收集


下一篇:对checkbox 的checked的一些总结