2022.2.3 训练日记2 P1083 [NOIP2012 提高组] 借教室

题目链接：借教室

题目分析：

0.二分答案 + 差分
1.参考以下题解

题解

code:

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1e6 + 10;int n, m;
int a[N];//每一天的可用数
//操作信息存储数组。
struct str
{
    int d, s, t;
}op[N];
int dc[N];//差分数组
bool check(int mid)
{
    for(int i = 1; i <= n; i ++) dc[i] = a[i] - a[i - 1];//求差分数组for(int i = 1; i <= mid; i ++){
    int d = op[i].d, s = op[i].s, t = op[i].t;dc[s] -= d, dc[t + 1] += d;}for(int i = 1; i <= n; i ++) {
    dc[i] = dc[i - 1] + dc[i];if(dc[i] < 0) return false;}return true;
}
int main()
{
    cin >> n >> m;for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);for(int i = 1; i <= m; i ++) {
    int d, s, t;scanf("%d%d%d", &d, &s, &t);//把每个信息读入op[i] = {
    d, s, t};}int l = 1, r = m + 1;while(l < r){
    int mid = l + r >> 1;if(check(mid)) l = mid + 1;else r = mid;}if(l == m + 1) cout << 0;else{
    cout << -1 << endl;cout << r;}return 0;
}

总结：

1.答案具有两半性就可以二分。
2.差分是将一个区间操作改为单点操作。