题目描述
根据c++来改写
样例
import java.io.*;
import java.util.*;
public class Main {
static int N = 1000010;
static int [] r = new int[N];
static int [] d = new int[N];
static int [] s = new int[N];
static int [] t = new int[N];
static long [] b = new long[N];
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] ss = br. readLine().split(" ");
n = Integer.parseInt(ss[0]);
int m = Integer.parseInt(ss[1]);
String[] s1 = br.readLine().split(" ");
for(int i = 1 ; i <= n ;i++){
r[i] = Integer.parseInt(s1[i-1]);
}
for (int i = n; i>=1; i -- ) {
r[i] -= r[i - 1];
}
for(int i =1 ;i<=m;i++){
String[] s2 = br.readLine().split(" ");
d[i] = Integer.parseInt(s2[0]);
s[i] = Integer.parseInt(s2[1]);
t[i] = Integer.parseInt(s2[2]);
}
int l =1 ,r = m ;
while (l<r){
int mid = l+r>>1;
if (check(mid)){
r = mid;
}else {
l = mid+1;
}
}
if (check(r)){
System.out.println("-1");
System.out.println(r);
}else {
System.out.println("0");
}
}
private static boolean check(int k) {
for (int i = 1; i <= n; i ++ ) {
b[i] = r[i];
}
for (int i = 1; i <= k; i ++ )
{
b[s[i]] -= d[i];
b[t[i] + 1] += d[i];
}
long res = 0;
for (int i = 1; i <= n; i ++ )
{
res += b[i];
if (res < 0) {
return true;
}
}
return false;
}
}