题解：CF1626C Monsters And Spells

日常写水题题解。

首先发现我们的魔力值是一条条斜率为 $1$ 一次函数。

对于第 $i$ 个怪物，不难发现 $k_i - h_i + 1$ 时刻的时候 $x$ 至少要是 $1$，我们记录这个时刻为 $p_i$。

做法就很显然了，我们从后往前遍历，每次维护当前对应魔力值直线对应的段末尾和开头的时间，如果当前怪物不在它后面这一段的开头时间之后，那就直接更新答案。否则就更新最早的开头时间就好。

感觉口胡的很乱，还是看代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n;
    cin >> n;
    vector<int> h(n), k(n);
    for (int i = 0; i < n; i++) {
        cin >> k[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    int ls = k[n - 1], t = k[n - 1] - h[n - 1] + 1;
    int ans = 0;
    for (int i = n - 2; i >= 0; i--) {
        if (t > k[i]) {
            ans += (2 + ls - t) * (1 + ls - t) / 2;
            ls = k[i];
            t = k[i] - h[i] + 1;
            continue;
        }
        t = min(t, k[i] - h[i] + 1);
    }
    ans += (2 + ls - t) * (1 + ls - t) / 2;
    cout << ans << '\n';
}
signed main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}