~~九级勾的萌新~~
by dying @ 2021-05-19 17:15:39
@[LiM_817](/user/56724) 给个码?/kk
by linfourxu @ 2021-05-19 17:33:02
```cpp
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i = (l); i <= (r); ++i)
#define per(i,r,l) for(int i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
inline int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return f * x;
}
const int N = 500010;
int n, m, o;
pair<int, int> order[N], rooms[N];
ll ans1 = 0;
priority_queue <int> q;
int check (ll x) {
ans1 = 0;
while (!q.empty()) q.pop();
int p = 1, res = 0;
rep (i, 1, n) {
while (p <= m && order[p].first <= rooms[i].first)
q.push(order[p].second), ++p;
if (!q.empty()) {
if (q.top() - x - rooms[i].second >= 0) {
// cerr << "PLACE " << rooms[i].second << " " << q.top() << '\n';
ans1 += q.top() - rooms[i].second;
q.pop();
++res;
}
}
}
// cerr << "RES = " << res << '\n';
return res;
}
int main() {
n = gi(), m = gi(), o = gi();
rep (i, 1, n) rooms[i].second = gi(), rooms[i].first = gi();
rep (i, 1, m) order[i].second = gi(), order[i].first = gi();
sort (rooms + 1, rooms + 1 + n);
sort (order + 1, order + 1 + m);
ll l = 0, r = 1e9, ans = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
ll cs = check(mid);
if (cs==o){
ans=mid;
break;
}
if (cs>o){
ans=mid;
l = mid + 1;
}
else r = mid - 1;
}
// cerr << "ANS = " << ans << '\n';
check(ans);
cout << (ll)ans1 << '\n';
return 0;
}
```
把 $l=0$ 改成 $l=-10^9$ 就不对了 /kk
by _LiM @ 2021-05-19 17:34:31
@[linfourxu](/user/50477)
by _LiM @ 2021-05-19 17:36:38
@[LiM_817](/user/56724) 这题不一定恰好选o个吧,我觉得你l=0可能是恰好对了,也就是一直都没切到,而你l=-1e就可以切到o了,然后答案就变小了
by linfourxu @ 2021-05-19 17:56:42
大佬!
by michael_song @ 2021-05-19 18:06:57