#题解#洛谷P1083借教室#二分#线段树#差分#

P1083 [NOIP 2012 提高组] 借教室 - 洛谷

分析

1. 答案单调，二分查找 。O（log m）

2. 每次查询一个mid，mid次区间修改：差分 or 线段树

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, m;
int s[N], t[N], r[N], d[N], dr[N], tmp1[N], tmp2[N];
bool check(int x)
{memcpy(tmp1, dr, sizeof(dr));for (int i = 1; i <= x; i++){tmp1[s[i]] -= d[i];tmp1[t[i] + 1] += d[i];}for (int i = 1; i <= n; i++){tmp2[i] = tmp2[i - 1] + tmp1[i];if (tmp2[i] < 0)return 0;}return 1;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++)cin >> r[i], dr[i] = r[i] - r[i - 1];for (int i = 1; i <= m; i++)cin >> d[i] >> s[i] >> t[i];int L = 0, R = m + 1;while (L < R){int mid = (L + R) / 2;if (check(mid))L = mid + 1;elseR = mid;}if (L > 0 && L < m + 1)cout << "-1\n" << L;elsecout << 0;return 0;
}