【链接】h在这里写链接

【题意】

    给你参赛者的数量以及一个整数S表示每块披萨的片数。

    每个参数者有3个参数,si,ai,bi;

    表示第i个参赛者它要吃的披萨的片数,以及吃一片第一种披萨增加的幸福感,

    以及吃一片第二种披萨增加的幸福感。

    两种披萨都能任意数量地订购。

    但是总数num有一个上限。

    就是S*num>=∑si

    且num最小。

    也就是说相当于给你一个num;

    让你求两种披萨各要买多少个a,b(a+b==num)。

    使得参赛者的幸福感尽可能高。

    (参赛者即可以选择第一种、也可以同时吃第二种)

【题解】

    如果每个人想要的披萨片数和<=S

    那么只能买一块披萨。

    则买a或买b,那么每个人都只能选A或选B

    取较大值就好。

    矛盾点在哪里?

        虽然你的a大,但是已经没有A披萨给你了

        或者,全都买B披萨更合适

    枚举最后买了多少个B披萨

    i=0

    则一开始全都吃A披萨

    i=1

    则让B-A前S大的人变成吃B披萨

    i=2

    则让B-A前2S大的人变成吃B披萨

    在i=i-1的基础上改一下就好

        记录到了哪一个人,那个人还能有多少从A->B

    i最大为num,且i*S<=∑si

    以B-A为关键字降序排一下?

【错的次数】

【反思】

加注释的方式真的很好。。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5;

struct abc{

    ll a,b,rest,c;

};

int n;

ll S,temp,num,srest,ans;

abc a[N+10];

bool cmp(abc a,abc b)

{

    return a.c > b.c;

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    scanf("%d%lld",&n,&S);

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

        scanf("%lld%lld%lld",&a[i].rest,&a[i].a,&a[i].b);

        a[i].c = a[i].b-a[i].a;

        temp += a[i].rest*a[i].a;

        srest += a[i].rest;

    }

    //获取最多买多少个披萨

    ll l = 1,r = 1e10 + 100;

    while (l <= r)

    {

        ll mid = (l+r)>>1;

        ll temp = mid*S;

        if (temp >= srest)

        {

            num = mid;

            r = mid - 1;

        }else

            l = mid + 1;

    }

    sort(a+1,a+1+n,cmp);//按照B-A降序排

    ans = temp;//一开始全都吃A披萨

    //这个num的值可能会很大,你可能不能枚举出来全部。

    //在可以的情况下,尽量贪心选。只要B披萨的数目不超过num就可以了

    ll temp1 = 0,tnum = 0;//tnum是之前剩余的变成B更优的个数

    //temp1是那些变成B之后答案的递增值

    ll spe = num*S-srest;//多买的披萨的片数

    //S片才能凑够一个B披萨

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

    {

        //第i个人有一些变成选B披萨

        if (a[i].c < 0)//这个人变成B之后答案会减小

        {//用spe尽量不让他减小->本来肯定要有一些人从a变成B,现在可以用多余的填,不用让他们变了

            //前提是

            if (tnum + a[i].rest + spe >= S)//够凑了

            {

                ll dd = tnum + spe;

                if (dd >= S)//不用加就能超过了

                {

                    ans = max(ans,temp + temp1);

                }else

                {

                    ll js = S-dd;

                    ans = max(ans,temp + temp1 + a[i].c*js);

                }

                temp1 = 0;

                break;

            }

        }

        if (tnum + a[i].rest < S)//如果没有超过了1块披萨的量

        {

            temp1 += a[i].rest*a[i].c;

            tnum += a[i].rest;

        }else//超过了

        {

            //这一个人的a->b选了多少个?

            temp += temp1;//优先加之前的

            ll rr = (a[i].rest + tnum)%S;//剩余的

            ll choose = a[i].rest-rr;//之后再加当前的

            temp += choose*a[i].c;

            tnum = rr;//前些轮的剩余变成rr了

            temp1 = rr*a[i].c;//temp1变成rr*a[i].c了

            ans = max(ans,temp);//取最大值

            //显然这个过程中B是肯定够用的

        }

    }

    //temp1 = 1;

    //printf("%lld\n",temp1);

    if (tnum + spe >= S)//全为正数最后一个剩下的可能还可以和多余的凑出来一个S

    {

        ans = max(ans,temp + temp1);

    }

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

    return 0;

}

巴特西

【Codeforces Round #437 (Div. 2) C】 Ordering Pizza