官方题解：[Algo Beat Contest 002.5 B] 草莓小蛋糕 (cakes)
joe_zxq
·
·
题解
这里是出题人的官方题解。
前言
“以后，或许不是永远。”
“我们，总会有交集的。”
## 解题分析
### 分析最优顺序
对于两种蛋糕 $i$ 和 $j$，我们需要确定谁应该先吃。
假设现在是第 $t$ 天，先吃 $i$ 再吃 $j$ 的总美味值为：
$$(D_i - (t-1) \times X_i) + (D_j - t \times X_j)$$
先吃 $j$ 再吃 $i$ 的总美味值为：
$$(D_j - (t-1) \times X_j) + (D_i - t \times X_i)$$
两者的差值为：
$$(D_i - (t-1) \times X_i + D_j - t \times X_j) - (D_j - (t-1) \times X_j + D_i - t \times X_i)$$
$$= - (t-1) \times X_i - t \times X_j + (t-1) \times X_j + t \times X_i$$
$$= X_i - X_j$$
因此得出结论：
- 当 $X_i > X_j$ 时，先吃 $i$ 更优。
- 当 $X_i < X_j$ 时，先吃 $j$ 更优。
- 当 $X_i = X_j$ 时，先吃哪个无所谓。
所以将蛋糕按 $X_i$ 降序排列后的顺序是最优的。
### 计算答案
我们考虑用初始时的总美味值减去因食物变质导致损失的美味值。
由于蛋糕数量可能很大，我们不能一天一天计算，需要批量处理同一种蛋糕。
对于第 $i$ 种蛋糕，假设从第 $s$ 天开始吃，连续吃 $C_i$ 天：
- 第一天（第 $s$ 天）的损失的美味值为 $(s-1) \times X_i$。
- 最后一天（第 $s+C_i-1$ 天）的美味值为 $(s+C_i-2) \times X_i$。
这是一个等差数列，用首项加末项乘项数除以 $2$ 的求和公式进行计算即可。
注意使用 `__int128` 处理大整数。
### 复杂度分析
- 时间复杂度：$O(N \log N)$，主要来自排序操作。
- 空间复杂度：$O(N)$，用于存储蛋糕信息。
## 代码实现
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
const ll N = 1e5 + 5;
ll tc = 1, n, cur;
i128 ans;
void write(i128 x);
struct cake { ll c, d, x; } a[N];
bool cmp(cake c1, cake c2) {
return c1.x > c2.x;
}
i128 sum(i128 l, i128 r, i128 x) {
return (l + r) * x / 2;
}
void solve() {
scanf("%lld", &n);
for (ll i = 1; i <= n; i++) {
scanf("%lld %lld %lld", &a[i].c, &a[i].d, &a[i].x);
i128 c = a[i].c, d = a[i].d;
ans += c * d;
}
stable_sort(a + 1, a + n + 1, cmp);
for (ll i = 1; i <= n; i++) {
ll c = a[i].c, x = a[i].x;
ans -= sum(cur * x, (cur + c - 1) * x, c);
cur += c;
}
write(ans);
}
int main() {
while (tc--) {
solve();
}
return 0;
}
void write(i128 x) {
if (x < 0) {
putchar('-'), x = -x;
}
if (x >= 10) {
write(x / 10);
}
putchar('0' + x % 10);
}
```