可以线段树或者二分。
线段树会被卡，二分写不好也会被卡。
所以用二分。
读入用getchar()的话可以减少一半以上的时间。
#include <cstdio> const int N = 1000000 + 9; long long delta[N]; int idx[N],a[N],n,m,d[N],s[N],t[N],pre; inline bool check(const int mid) { long long sum = 0; if (pre < mid) for (int i = pre + 1; i <= mid; ++i) delta[s[i]] += d[i],delta[t[i] + 1] -= d[i]; else for (int i = mid + 1; i <= pre; ++i) delta[s[i]] -= d[i],delta[t[i] + 1] += d[i]; pre = mid; for (int i = 1; i <= n; ++i) if ((sum += delta[i]) > a[i]) return false; return true; } inline void read(int &x) { char c; while ((c = getchar()) < '0'); while (c >= '0') { x = x * 10 + c - '0'; c = getchar(); } } int main() { #ifndef ONLINE_JUDGE freopen("classroom.in","r",stdin); freopen("classroom.out","w",stdout); #endif read(n);read(m); for (int i = 1; i <= n; ++i) read(a[i]); for (int i = 1; i <= m; ++i) { read(d[i]);read(s[i]);read(t[i]); } int l = 0,r = n + 1; while (l + 1 < r) { const int mid = (l + r)/2; if (check(mid)) l = mid; else r = mid; } if (l == n) puts("0"); else printf("-1\n%d\n",r); }
转载于:https://www.cnblogs.com/lazycal/p/noip2012-day2-t2.html
相关资源：JAVA上百实例源码以及开源项目