AcWing 499. 聪明的质监员(Java)
原题链接
简单
作者:
上杉
,
2021-02-05 09:45:02
,
所有人可见
,
阅读 472
java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
long S = input.nextLong();
int[] w = new int[n];
int[] v = new int[n];
int[][] secs = new int[m][2];
for (int i = 0; i < n; i++) {
w[i] = input.nextInt();
v[i] = input.nextInt();
}
for (int i = 0; i < m; i++) {
secs[i][0] = input.nextInt() - 1;
secs[i][1] = input.nextInt() - 1;
}
int l = 0;
int r = 1000001;
long res = Long.MAX_VALUE;
while (l < r){
int W = ( l + r + 1) / 2;
long Y = calY(w, v, secs, W);
res = Math.min(res,Math.abs(Y - S));
if (Y >= S){
l = W ;//L左边的 Y >= S
// R 右边的Y < S
}else {
r = W - 1;
}
}
//system.out.println(calY(w, v, secs, 8139));
System.out.println(res);
}
private static long calY(int[] w, int[] v, int[][] secs, int W) {
int[] count = new int[w.length + 1];
long[] sum = new long[w.length + 1];
for (int i = 0; i < w.length; i++) {
if (w[i] >= W){
count[i + 1] = 1;
sum[i + 1] = v[i];
}
count[i+1] += count[i];
sum[i+1] += sum[i];
}
long Y = 0;
for (int[] sec : secs) {
int l = sec[0];
int r = sec[1];
Y += (count[r + 1] - count[l]) * (sum[r+1] - sum[l]);
}
return Y;
}
}