题解 P5117 【[USACO18DEC]The Bucket List】

_Qer · 2019-03-22 19:17:09 · 题解

裸差分吧，虽然数据水暴力随便锤

对于每个s,t,b，标记从s到t间需要的桶数量加上b，用差分来搞，一个p数组，p_i表示i+1时刻比i时刻需要的桶数多p_i，那么对于每头牛，p_{s-1}就要加b，p_t就减b，最后求前缀和再取个max就完事了。

#include <bits/stdc++.h>
using namespace std;
int n, s, t, b, p[1010];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &s, &t, &b);
        p[s - 1] += b, p[t] -= b;
    }
    int ans = 0, h = 0;//h即前缀和
    for (int i = 0; i <= 1001; ++i) {
        ans = max(ans, h);
        h += p[i];
    }
    cout << ans << endl;
    return 0;
}