二分检验+差分
#include <iostream> using namespace std; const int maxn = 1000010; int n, m; long long arr[maxn];//每天借多少个教室 long long arr2[maxn];//教室差分 struct Node { long long num; int beginDay; int endDay; }dingdan[maxn]; bool judge(int num) { for (int i = 0; i < maxn; i++) { arr2[i] = 0; } int sum = 0; for (int i = 1; i <= num; i++) { arr2[dingdan[i].beginDay] += dingdan[i].num; arr2[dingdan[i].endDay + 1] -= dingdan[i].num; } for (int i = 1; i <= n; i++) { sum += arr2[i]; if (sum > arr[i])return false; } return true; } int find(int l, int r) { while (l < r) { int mid = (r - l) / 2 + l; if (judge(mid))l = mid + 1; else r = mid; } return l; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> arr[i]; } for (int i = 1; i <= m; i++) { cin >> dingdan[i].num >> dingdan[i].beginDay >> dingdan[i].endDay; } if (find(1, m) < m) { cout << "-1" << endl << find(1, m); } else { cout << "0"; } }