前言
。
“以后，或许不是永远。”
“我们，总会有交集的。”
解题分析
分析最优顺序
对于两种蛋糕 和 ，我们需要确定谁应该先吃。
假设现在是第 天，先吃 再吃 的总美味值为：
先吃 再吃 的总美味值为：
两者的差值为：
因此得出结论：
- 当 时，先吃 更优。
- 当 时，先吃 更优。
- 当 时，先吃哪个无所谓。
所以将蛋糕按 降序排列后的顺序是最优的。
计算答案
我们考虑用初始时的总美味值减去因食物变质导致损失的美味值。
由于蛋糕数量可能很大，我们不能一天一天计算，需要批量处理同一种蛋糕。
对于第 种蛋糕，假设从第 天开始吃，连续吃 天：
- 第一天（第 天）的损失的美味值为 。
- 最后一天（第 天）的美味值为 。
这是一个等差数列，用首项加末项乘项数除以 的求和公式进行计算即可。
注意使用 __int128 处理大整数。
复杂度分析
- 时间复杂度：，主要来自排序操作。
- 空间复杂度：，用于存储蛋糕信息。
代码实现
#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);
}
暂无评论