思路
$A,B$ 有$10^9$的量级,但是有用的只有 $20000$ 不到所以使用字典离散化温度坐标,且给出了最大温度与最小温度,又问求最大的产奶量,且最大产奶量与区间($x,y,z$)中的牛有关,是较为经典的区间操作,使用差分
python3 代码
from collections import defaultdict;
def main():
n,x,y,z = map(int,input().split());
f = defaultdict(int); #使用字典模拟差分数组
right = defaultdict(int); #使用字典模拟前缀和数组
for _ in range(1,n + 1):
a,b = map(int,input().split());
f[a] += 1;
if b not in f:f[b] = 0; #防止将多次重复出现的值置0 这段也可以不要,我们只要找到一个最大值就可以了
f[b + 1] -= 1;
right[a] += 1; #用来统牛的前缀和
cnt = 0; #温度适宜的牛数
res = 0; #全局结果变量
S = 0; #在left时一个有S头牛
for left in sorted(f):
cnt += f[left];
if left in right: S += right[left]
ans = (n - S) * x + cnt * y + (S - cnt) * z; #选取温度为left时的产奶量
if ans > res:
res = ans;
print(res);
main();
咋一看我还以为是和这道一样的acwing110.防晒贪心题来着,还都是奶牛都有最大最小值的限制QAQ