分析
将 ai 和 bi 映射到数轴上, [0, ai) 为 x ,[ai, bi] 为 y,(bi, +00) 为 z,显然是差分
因为 ai bi 数据范围很大,需要离散化
差分:a[0] += x, a[find(ai)] -= x, a[find(ai)] += y, a[find(bi + 1)] -= y, a[find(bi + 1)] += z
题目可以理解为将多组 ai bi 差分到同一个数轴,求前缀和最大值
注意(使用 map 不需要)
- a[] 数组最大长度是 4e4
- 记录点时要把 0 和 bi + 1 也记录
代码 1 - map
#include <bits/stdc++.h>
using namespace std;
int n, x, y, z, ai, bi;
map<int, int> mp;
int main()
{
cin >> n >> x >> y >> z;
for (int i = 0; i < n; i++) {
scanf("%d %d", &ai, &bi); mp[0] += x, mp[ai] += y - x, mp[bi + 1] += z - y;
}
int maxn = -1, tot = 0;
for (auto &item : mp) { // 重点 不能是从 0 循环到 ai或bi 最大值
tot += item.second; maxn = max(maxn, tot);
}
printf("%d", maxn);
return 0;
}
代码 2
#include <bits/stdc++.h>
using namespace std;
const int N = 40010;
int n, x, y, z, ai, bi;
int a[N], s[N], A[N / 2], B[N / 2];
vector<int> all;
int find(int x) {
int l = 0, r = all.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (all[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
int main()
{
cin >> n >> x >> y >> z; all.push_back(0); // 0 也要存入
for (int i = 0; i < n; i++) {
scanf("%d %d", &ai, &bi);
all.push_back(ai), all.push_back(bi), all.push_back(bi + 1);
A[i] = ai, B[i] = bi;
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
for (int i = 0; i < n; i++) {
a[find(0)] += x, a[find(A[i])] += y - x, a[find(B[i] + 1)] += z - y;
}
int maxn = -1;
for (int i = 0; i < 2 * n + 1; i++) {
s[i] = s[i - 1] + a[i];
maxn = max(maxn, s[i]);
}
printf("%d", maxn);
return 0;
}