AcWing 503. 借教室(Java 使用scanner会超时)
原题链接
简单
作者:
上杉
,
2021-02-06 09:17:51
,
所有人可见
,
阅读 609
java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] split = reader.readLine().split(" ");
int n = Integer.parseInt(split[0]);
int m = Integer.parseInt(split[1]);
int[] count = new int[n + 1];
String[] cns = reader.readLine().split(" ");
for (int i = 1; i <= n ; i++) {
count[i] = Integer.parseInt(cns[i-1]);
}
for (int i = n ; i >= 1 ; i--){
count[i] -= count[i-1];
}
int[][] orders = new int[m + 1][3];
for (int i = 1; i <=m ; i++) {
String[] ods = reader.readLine().split(" ");
orders[i][0] = Integer.parseInt(ods[0]);
orders[i][1] = Integer.parseInt(ods[1]);
orders[i][2] = Integer.parseInt(ods[2]);
}
reader.close();
int l = 1;
int r = m;
while (l < r){
int mid = (l + r) / 2;
boolean flag = check(count,orders,mid);
if (flag){//mid的位置可以
l = mid + 1;
}else {//mid的位置不可以
r = mid;
}
}
if (check(count,orders,r)){
System.out.println(0);
}else {
System.out.println(-1);
System.out.println(r);
}
}
private static boolean check(int[] count, int[][] orders, int mid) {
//复制差分数组
long[] copy = new long[count.length];
for (int i = 1; i < copy.length ; i++) {
copy[i] = count[i];
}
//将第一天到第mid天的教室减去
for (int i = 1; i <= mid ; i++) {
//orders[i][0] 第i个订单所需教室数,orders[i][1]起始天数 orders[i][2]结束天数
//orders[i][1];
copy[orders[i][1]] -=orders[i][0];
if (orders[i][2] != copy.length - 1){
copy[orders[i][2] + 1] += orders[i][0];
}
}
long res = 0;
for (int i = 1; i < copy.length ; i++) {
res = res + copy[i];
if (res < 0){
return false;
}
}
return true;
}
}
确实超时.....