[NOIP2012 提高组] 借教室 - 洛谷
差分
针对区间操作,在本题中体现为多次对序列的区间加上一个数
对差分数组的操作为,
diff[l] += k;
diff[r+1] -= 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;
} else
r = mid;
}
cout << "-1" << endl << l << endl;
return 0;
}