算法1
(奇怪の做法) $O(nlogn)$
没有用差分,就是离散,暴力
比map快
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 20010;
int n, X, Y, Z;
PII q[2 * N];
int main()
{
cin >> n >> X >> Y >> Z;
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
q[i << 1] = {a, 0};
q[(i << 1) + 1] = {b, 1};
}
sort(q, q + (n << 1));
int l = n, mid = 0, res = 0;
for(int i = 0; i < 2*n; i ++){
PII k = q[i];
// cout << k.x << " " << k.y << '\n';
if(!k.y)
{
mid ++;
l --;
}
else
{
mid --;
}
res = max(res, mid * Y + l * X + (n - mid - l) * Z);
}
cout << res << endl;
return 0;
}
算法2
(yの手写离散化做法) $O(nlogn)$
比我快了20ms, Orz
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 20010, INF = 2e9;
int n, x, y, z;
vector<int> xs;
int l[N], r[N], b[N * 2];
int find(int v)
{
int l = 0, r = xs.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (xs[mid] >= v) r = mid;
else l = mid + 1;
}
return r;
}
int main()
{
scanf("%d%d%d%d", &n, &x, &y, &z);
xs.push_back(-INF), xs.push_back(INF);
for (int i = 0; i < n; i ++ )
{
scanf("%d%d", &l[i], &r[i]);
xs.push_back(l[i]);
xs.push_back(r[i] + 1);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 0; i < n; i ++ )
{
int L = find(l[i]), R = find(r[i] + 1);
b[0] += x;
b[L] += y - x;
b[R] += z - y;
b[xs.size() - 1] -= z;
}
int res = 0, sum = 0;
for (int i = 0; i < xs.size(); i ++ )
{
sum += b[i];
res = max(res, sum);
}
printf("%d\n", res);
return 0;
}