柚子快报激活码778899分享：蓝桥杯——泡澡
题目没有给n的范围，让我天真的以为数据不会太大，结果又写了个超时的代码，具体如下：
#include
using namespace std;
using ll = long long;
const int maxn = 1e6;
ll P[maxn];
ll d[maxn];
int main()
{
int n;
ll w;
cin >> n >> w;
for (int i = 1; i <= n; i++){
int s, t, p; cin >> s >> t >> p;
for (int i = 1; i <= t - s; i++) {
P[i] += p;
if (P[i] > w){
cout << "No";
return 0;
}
}
}
cout << "Yes";
return 0;
}
思路很简单，就是双重循环，每次检测P数组的值是否大于w。但又又又又又超时啦！
差分
这题依然是用差分解决。其实题目中给了范围s~t，就给人一种前缀和或者差分的感觉。结果果然是要用差分。区别于普通差分模板，这的一个关键在于默认差分数组中一开始所有元素均为0。之后的每一个人都是在这个0的基础上对区间进行加p的操作。（ps：这里的差分数组表示的是每分钟需要的泡澡水的差分，跟人数n没有一点关系！）之后只要在依次遍历差分数组，对差分数组的前缀和与w作比较，判断以下输出即可。
这题在差分时有个小坑。就是s的取值可能为0。众所周知，差分数组的下标是从1取起的，所以需要将s~t的区间向后移1个单位即可，保证差分数组下标为0的元素值一定为0。
#include
using namespace std;
using ll = long long;
const int maxn = 1e6;
ll d[maxn];
int main()
{
int n;
ll w;
int maxt = 0;
cin >> n >> w;
for (int i = 1; i <= n; i++){
int s, t, p; cin >> s >> t >> p;
maxt = max(t, maxt);
d[s + 1] += p;
d[t + 1] -= p;
}
for(int i = 1; i <= maxt; i++){
d[i] += d[i - 1];
if (d[i] > w){
cout << "No";
return 0;
}
}
cout << "Yes";
return 0;
}
柚子快报激活码778899分享：蓝桥杯——泡澡
参考文章
您阅读本篇文章共花了：
发表评论