Luogu

LOJ

分析

先考虑没有 $o$ 的限制怎么做。可以想到贪心，把房间按容量小到大排序、订单按人数从小到大排序，然后依次枚举每个房间，选择能容纳的租金最高的那个订单。正确性比较显然。

现在加入这个限制，可以考虑 WQS 二分。设 $f(x)$ 表示接受 $x$ 个订单的最大收入，感性理解可以知道 $f(x)$ 是凸的。二分斜率 $m$，则我们要求最大的 $b=f(x)-mx$，而这个东西可以看成每个订单的租金减去了 $m$，这样子套用上面的贪心即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n,m,o;
struct room { int c,p; } a[N];
bool operator <(room a,room b) { return a.p<b.p||(a.p==b.p&&a.c<b.c); }
struct guest { int v,d; } b[N];
bool operator <(guest a,guest b) { return a.d<b.d||(a.d==b.d&&a.v>b.v); }

pair<int,ll> calc(int mid) {
    priority_queue<int> Q;
    int cnt=0; ll res=0;
    for (int i=1,j=1;i<=n;++i) {
        while (j<=m&&b[j].d<=a[i].p) Q.push(b[j].v-mid),++j;
        if (!Q.empty()) {
            int w=Q.top();
            if (w>a[i].c) ++cnt,res+=w-a[i].c,Q.pop();
        }
    }
    return make_pair(cnt,res);
}

int main() {
    n=read(),m=read(),o=read();
    for (int i=1;i<=n;++i) a[i]=(room){read(),read()};
    for (int i=1;i<=m;++i) b[i]=(guest){read(),read()};
    sort(a+1,a+n+1),sort(b+1,b+m+1);
    int L=0,R=1e9;
    while (L<R) {
        int mid=(L+R)>>1;
        if (calc(mid).first<=o) R=mid;
        else L=mid+1;
    }
    printf("%lld\n",calc(L).second+1ll*L*o);
    return 0;
}