算法1
(差分)
对于每个温度值,必然置于[0 , A), [A , B], (B , 10^9]这三个区间,分别能获取牛奶 X, Y, Z,显而易见可以使用差分的方法
但是该题数据范围为 10^9,无法使用数组,所以采用 Map 来存储
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Map;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
String str = in.readLine();
int n = Integer.parseInt(str.split(" ")[0]);
int x = Integer.parseInt(str.split(" ")[1]);
int y = Integer.parseInt(str.split(" ")[2]);
int z = Integer.parseInt(str.split(" ")[3]);
Map<Integer, Integer> tempreture = new TreeMap<Integer, Integer>(); // TreeMap 默认按 key 值的字典序升序
for(int i = 0; i < n; i++) {
str = in.readLine();
int start = Integer.parseInt(str.split(" ")[0]);
int end = Integer.parseInt(str.split(" ")[1]);
try {
tempreture.put(0, tempreture.get(0) + x);
} catch (Exception e) {
tempreture.put(0, x);
}
try {
tempreture.put(start, tempreture.get(start) - x + y);
} catch (Exception e) {
tempreture.put(start, - x + y);
}
try {
tempreture.put(end + 1, tempreture.get(end + 1) - y + z);
} catch (Exception e) {
tempreture.put(end + 1, - y + z);
}
}
int max = 0;
int current = 0;
for(int key : tempreture.keySet()) {
current += tempreture.get(key);
max = Math.max(max, current);
}
out.print(max);
out.flush();
}
}