题解：P14167 [Algo Beat Contest 002.5 B] 草莓小蛋糕 (cakes)

题目描述：

1. $n$ 种蛋糕
2. 每种 $Ai$ 块
3. 每种第一天 $Bi$ 的值
4. 每天降低 $Ci$

思路：

让我们求最大美味值，显而易见是贪心，故可有以下思路：
将降低快的先吃了，使得减少值最小。故有了标签排序
不过值得一提的是这里要用 __128int 。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
//照题意使用
__int128 read() {char c;bool isf = 0;while (!isdigit(c = getchar())) {isf = (c == '-');}__int128 res = (c ^ 48);while (isdigit(c = getchar())) {res = (res << 3) + (res << 1) + (c ^ 48);}return isf ? -res : res;
}
void write(__int128 x) {if (x < 0) {putchar('-'), x = -x;}if (x >= 10) {write(x / 10);}putchar('0' + x % 10);
}
//结构体存蛋糕
struct CK{__int128 a,b,c;
}ck[100010];
//不想重构运算符
bool cmp(CK a,CK b){return a.c>b.c;//按美味值的降低降序排列
}
int n;
int main(){//输入。。scanf("%d",&n);__int128 s=0;for(int i=1;i<=n;i++){__int128 a=read(),b=read(),c=read();s+=a*b;ck[i]={a,b,c};}//排序，记得用cmp。sort(ck+1,ck+n+1,cmp);__int128 d=0,cnt=0;//衰减总值，天数for(int i=1;i<=n;i++){__int128 a=ck[i].a,c=ck[i].c;d+=c*(a*(a-1)/2)+a*c*cnt;//第cnt天减了的cnt+=a;//加上蛋糕数}write(s-d);//用总值减puts("");return 0;
}