CF1626C Solution
feicheng
·
·
题解
CF1626C Solution
Description
有 n 个怪物，对于第 i 个怪物，你需要在第 k_i 秒打死它，它的血量值为 h_i。
第一秒时你的法术攻击力为 1，对第 z 秒时，如果在第 z-1 秒你没有释放法术，那么你的攻击力为 0，若释放了，假设在 z-1 秒时法术攻击力为 x，则这一秒你的法术可以变为 x+1 或 1。
释放一个攻击力为 x 的法术需要消耗 x 法力，你需要在打死所有怪物的前提下，最小化法力消耗。
多测。
## Solution
容易发现对于两个怪物之间可以增加的伤害值为 $\Delta k=k_i-k_{i-1}$，如果下一个怪物的生命值 $h_i\le \Delta k$，那么可以直接在这一轮伤害变为 $1$，否则需要保持上一轮的伤害不变。
但是这样子是有缺陷的：
考虑如下数据
```
1000000 1000001 1000002
1000000 1 1000001
```
这样子的话在第二个怪向第三个怪转的时候就没有足够的伤害去打了。
所以我们发现**一个时间点需要达到的法力值是和之后的怪物的生命值相关的**，换言之，设 $f_i$ 表示到第 $i$ 个怪物时需要的法力值，则 $f_i=\max\{h_i,f_{i+1}-\Delta k\}$。
对第 $m$ 个怪物，考虑对 $f_m-d$ 分类讨论（$d$ 为在第 $m-1$ 个怪物时的伤害）。
1. $f_m-d\leq k_m-k_{m-1}$：此时可以将伤害变为 $1$，因为可以增加到 $f_m$，产生了 $\dfrac{f_m\times (f_m+1)}{2}$ 的花费。
2. 反之，这时伤害不能归 $1$，产生了 $\dfrac 1 2(2d+\Delta k)\times \Delta k$ 的花费。
于是我们在 $\Theta\left(\sum n\right)$ 的时间复杂度解决了这个问题。
## Code
```cpp
// Author:Feicheng
/* -------- Main part of the Program--------*/
#include <bits/stdc++.h>
using std::cin;
using std::cout;
constexpr int N = 110;
int n, T;
long long h[N], k[N], f[N];
inline void clear() {
memset(h, 0, sizeof h);
memset(k, 0, sizeof k);
memset(f, 0, sizeof f);
}
inline long long calc(long long st, long long ed, long long num) {
return (st + ed) * num / 2ll;
}
inline void solve() {
clear();
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> k[i];
}
for (int i = 1; i <= n; ++i) {
cin >> h[i];
}
f[n] = h[n];
for (int i = n - 1; i >= 1; --i) {
auto delta = k[i + 1] - k[i];
f[i] = std::max(f[i + 1] - delta, h[i]);
}
long long ans = calc(1, f[1], f[1]), d = f[1];
// cout << ans << '\n';
for (int i = 1; i < n; ++i) {
auto delta = k[i + 1] - k[i];
if (f[i + 1] <= delta) {
ans += calc(1, f[i + 1], f[i + 1]);
d = f[i + 1];
}
else {
ans += calc(d + 1, d + delta, delta);
d += delta;
}
}
cout << ans << '\n';
}
int main(int argc, const char** argv) {
#ifdef Feicheng
freopen("input.in", "r", stdin);
freopen("output.ans", "w", stdout);
#endif
std::basic_ios<char>::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
for (; T; --T) {
solve();
}
return 0;
}
```