【基础】Atcoder-ABC183-D-Water Heater【差分】

传送门

D - Water Heater

题意

有一个热水器，每秒钟提供W/升的热水。

有N个人，第(i)个人在(S_i)-(T_i)这个时间段内要用(P_i)升热水。

问你热水器每秒钟提供的热水是否够他们使用，如果可以的话输出Yes，否则输出No.

思路

考虑差分前缀和，某段时间内使用的热水量实际是n个人在这个区间内的综合，那么第(i)个人的贡献实际是对于S：

sum[s]+=p

对于T:

sum[t]-=p

其中sum数组是差分数组。

然后从最小的时刻开始一直对sum数组求和到最大的时刻，如果在这期间总量超过了W，输出No，否则输出Yes.

AC代码

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2e5+10;
                        
ll sum[maxn];
int main(void){
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int n,w;   
    cin >> n >> w;
    int maxx = 0;
    for(int i = 1; i <= n; i++){
        int s,t,p;
        cin >> s >> t >> p;
        maxx = max(maxx,t);
        sum[s] += p;
        sum[t] -= p;
    }
    ll ans = 0;
    bool flag = 0;
    for(int i = 0; i < maxx; i++){
        ans += sum[i];
        if(ans>w){
            flag = 1;
            break;
        }
    }
    if(flag) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}