做个个人网站多少钱,百度小程序开发教程,许昌网站制作,唐山滦县网站建设[NOIP2012 提高组] 借教室 - 洛谷
差分
针对区间操作#xff0c;在本题中体现为多次对序列的区间加上一个数
对差分数组的操作为#xff0c; diff[l] k; diff[r1] - k; 最后通过前缀和来实现整个区间加上一个数的效果。
二分
大多数人对于二分的基础印象可能是#xf…[NOIP2012 提高组] 借教室 - 洛谷
差分
针对区间操作在本题中体现为多次对序列的区间加上一个数
对差分数组的操作为 diff[l] k; diff[r1] - k; 最后通过前缀和来实现整个区间加上一个数的效果。
二分
大多数人对于二分的基础印象可能是升序的序列查找某个值如果该值中间值则去左侧寻找如果改值中间值则去右侧寻找。
但通过比大小来进行二分只是冰山一角二分更基本的实质体现在下面所说的。
对于能否二分有一个界定标准状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。
也就是说序列是有序的而这里的“有序”是指广义的有序如果一个数组中的左侧或者右侧都满足某一种条件而另一侧都不满足这种条件也可以看作是一种有序。
在本题中体现为如果第k天能够满足则前k天必能够满足若第k天不能满足则第k天以后都不能满足借教室的需求。 题解
#include iostream
#include cstring
using namespace std;const int maxn 1e6 5;
long long s[maxn], t[maxn], d[maxn], r[maxn], diff[maxn], need[maxn];
int n, m;bool canBorrow(int x) {memset(diff, 0, sizeof(diff));for (int i 1; i x; i) {diff[s[i]] d[i];diff[t[i] 1] - d[i];}for (int i 1; i n; i) {need[i] need[i - 1] diff[i];//cout i need: need[i] endl;if (need[i] r[i])return false;}return true;
}int main() {cin n m;for (int i 1; i n; i)cin r[i];for (int i 1; i m; i)cin d[i] s[i] t[i];if (canBorrow(m)) {cout 0\n;return 0;}long long l 1, r m;while (l r) {long long mid (l r) / 2;if (canBorrow(mid)) {l mid 1;} elser mid;}cout -1 endl l endl;return 0;
}
