题目描述
当奶牛温度 < a 时 可以产奶 x
当奶牛温度>= a && 奶牛温度 <= b 可以产奶 y
当奶牛温度 > b 可以产奶 z
因为温度 <= 1e9 所以需要离散化.
差分数组只需要开 2 * N 即可, 因为 最多有N 头奶牛只会给出2 * N个温度.
(差分) $O(nlogn)$
C++ 代码
//3 4 5 7 8 10 13 20
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
vector<int>alls;
vector<PII>add;
int b[40010];
int find(int x)
{
int l = 0, r = alls.size() - 1;
while ( l < r )
{
int mid = (l + r) >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
int main()
{
int n, x, y, z;
cin >> n >> x >> y >> z;
for(int i = 1; i <= n; ++ i)
{
int x, y;
cin >> x >> y;
alls.push_back(x);
alls.push_back(y + 1);
add.push_back({x, y + 1});
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for(int i = 0; i < n; ++ i)
{
int x1 = find(add[i].first), y1 = find(add[i].second);
//[1, x1 - 1) + x;
//[x1, y1] + y;
//(y1, size) + z;
b[1] += x;
b[x1] += y - x;
b[y1] += z - y;
}
int res = 0;
for(int i = 1; i <= alls.size(); ++ i) b[i] += b[i - 1];
for(int i = 1; i <= alls.size(); ++ i) res = max(res, b[i]);
cout << res;
return 0;
}