对于每一头牛,温度都有三个区间:
1. [0, A - 1] 产奶量为x
2. [A, B] 产奶量为y
3. [B + 1, $\ldots$] 产奶量为z
暴力枚举每一种温度的产奶量超时,可以把上述三个区间做差分:
1. [0, A - 1] 产奶量为 x
2. [A, B] 产奶量为 y - x
3. [B + 1, $\ldots$] 产奶量为 z - y
这样求每一种温度,只需要求它的前缀和即可。
由于温度是离散量(最多40000个数量),但数值较大,可以开 map 存储。
#include <bits/stdc++.h>
using namespace std;
int n, x, y, z;
map<int, int> p;
int main ()
{
cin >> n >> x >> y >> z;
for (int i = 1, l, r; i <= n && cin >> l >> r; i ++ )
{
p[0] += x;
p[l] += y - x;
p[r + 1] += z - y;
}
int ret = 0, sum = 0;
for (auto & [k, v] : p)
{
sum += v;
ret = max(ret, sum);
}
cout << ret << endl;
return 0;
}