题目链接:
D - Water Heaterhttps://atcoder.jp/contests/abc183/tasks/abc183_d
题目大意:
一个热水器,每分钟可以提供 W 升热水,现在有 N 个人使用,第 i 个人每分钟要用 Pi 升热水,从 Si 时间开始到 Ti 结束(不包括 Ti 时间点)。问给出的使用计划是否可行。
思路:
这题并不难,主要是要用到一个特殊的方法:前缀和
但是如果直接模拟的话,每个区间内所有值都要加上对应的值,复杂度是O(N^2),会超时。而用前缀和,就只需要记录第一个值和最后一个值,然后用一个int sum遍历整个数组,中间判断是否有超过W即可,这就降低到O(N)复杂度。详细见代码:
代码:
#include <iostream>
#include <iomanip>
#include <cmath>
#include <climits>
typedef long long ll;
using namespace std;
const int MAXN = 2e6+5;
const int MAXT = 2e5+5;
//分析:N是2e5,暴力法O(N^2)会超时
//所以本题要用到前缀和解法,优化到O(N)(新技能get)ll cost[MAXN];
int main(){//快读ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//输入ll n, w;cin >> n >> w;ll s, t, curCost;for(int i=1; i<=n; i++){cin >> s >> t >> curCost;cost[s] += curCost;cost[t] -= curCost;}//之前WA的原因:没有检查time = 0的时候是否可以for(int i=1; i<=MAXT+1; i++){cost[i] += cost[i-1];if(cost[i-1] > w) {cout << "No" << endl; return 0;}}cout << "Yes" << endl;return 0;
}