【链接】h在这里写链接
【题意】
给你参赛者的数量以及一个整数S表示每块披萨的片数。
每个参数者有3个参数,si,ai,bi;
表示第i个参赛者它要吃的披萨的片数,以及吃一片第一种披萨增加的幸福感,
以及吃一片第二种披萨增加的幸福感。
两种披萨都能任意数量地订购。
但是总数num有一个上限。
就是S*num>=∑si
且num最小。
也就是说相当于给你一个num;
让你求两种披萨各要买多少个a,b(a+b==num)。
使得参赛者的幸福感尽可能高。
(参赛者即可以选择第一种、也可以同时吃第二种)
每个参数者有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为关键字降序排一下?
那么只能买一块披萨。
则买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为关键字降序排一下?
【错的次数】
0
【反思】
加注释的方式真的很好。。
【代码】
#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
",temp1);
if (tnum + spe >= S)//全为正数最后一个剩下的可能还可以和多余的凑出来一个S
{
ans = max(ans,temp + temp1);
}
printf("%lld
",ans);
return 0;
}