二分+前缀和+差分
题目求第一个不满足条件的订单号
即左满足右不满足,具有单调性,可采用二分
二分关键搞懂枚举内容:本题中就是左满足右不满足中寻找第一个不满足的订单
不满足订单号范围(l,r范围):[1,m+1] ps:当值为m+1时,表示未找到
本题代码l= mid+1 ,因此int mid = l + r >> 1即可
java 代码
import java.io.*;
public class Main {
static int n, m;
static int[] r;
static int[] d;
static int[] s;
static int[] t;
static boolean check(int mid){
long []tmp = new long[n+2];
for(int i=1;i<=mid;i++){
tmp[s[i]]+=d[i];
tmp[t[i]+1]-=d[i];
}
long sum = 0;
for(int i =1;i<=n;i++) {
sum+=tmp[i];
if(sum>r[i])
return false;
}
return true;
}
public static void main(String[] args)throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String[] line = in.readLine().split(" ");
n = Integer.parseInt(line[0]);
m = Integer.parseInt(line[1]);
r = new int[n+1];
d = new int[m+1];
s = new int[m+1];
t = new int[m+1];
line = in.readLine().split(" ");
for(int i=1;i<=n;i++){
r[i] = Integer.parseInt(line[i-1]);
}
for(int i=1;i<=m;i++){
line = in.readLine().split(" ");
d[i] = Integer.parseInt(line[0]);
s[i] = Integer.parseInt(line[1]);
t[i] = Integer.parseInt(line[2]);
}
int l = 1;
int r = m+1;
while(l<r) {
int mid = l+r >>1;
if(check(mid))
l = mid +1;
else
r = mid;
}
if(l==m+1){
out.write("0");
}
else{
out.write("-1\n");
out.write(l+"");
}
out.flush();
out.close();
in.close();
}
}