题目描述
blablabla
样例
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
算法1
(二分 + 差分) $O((m + n) * logn)$
import java.io.*;
public class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int nextInt() throws Exception{in.nextToken(); return (int) in.nval;}
static int n,m,N = 1000010;
//第i天有多少教室
static int[] room = new int[N],d = new int[N],s = new int[N],t = new int[N];
public static void main(String[] args) throws Exception {
n = nextInt();m = nextInt();
for(int i = 1; i <= n; i++) room[i] = nextInt();
for(int i = 1; i <= m; i++) {
d[i] = nextInt();s[i] = nextInt();t[i] = nextInt();
}
int l = 1,r = m + 1;//订单数即申请人编号 有几个订单数编号排到几
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) {//check订单数是否多了
r = mid;
} else {
l = mid + 1;
}
}
if(r == m + 1) System.out.println(0);//可以到m + 1说明订单都可行 不然到不了m + 1
else System.out.println(-1 + "\n" + r);
}
public static boolean check(int mid) {
long[] temp = new long[N];
for(int i = 1; i <= mid; i++) {
temp[s[i]] += d[i];
temp[t[i]+1] -= d[i];
}
for(int i = 1; i <= n; i++) {
temp[i] += temp[i-1];
if(temp[i] > room[i]) return true;//说明借的教室比有的多了 订单数超了
}
return false;
}
}