蒟蒻的小窝

蒟蒻的小窝

题解 P4698 【[CEOI2011]Hotel】

posted on 2020-11-28 10:21:01 | under 题解 |

此题有一个隐含的道理,当我们按照人数由大到小,人数相同打扫所需费用由大到小时,你会发现此时的房间打扫费用绝对是单调不升的。

那么二分按照所需人数定位到满足条件的最后一个的时候绝对是此时最优的选择,当然这个位置有可能被占用了,占用为 $1$,你会发现你标记一会儿 $1$ 就联成一片,哎呦喂并查集立马登场,至此完美解决!

#include<bits/stdc++.h>
#define LL long long
#define maxn 500005
using namespace std;
int N,M,O,pre[maxn],Mon[maxn];
LL Ans;
struct Room{
    int cos,p;
    bool operator <(const Room B)const{return B.p<p||B.p==p&&B.cos<cos;}
}a[maxn];
struct Custom{
    int val,num;
    bool operator <(const Custom B)const{return B.val<val||B.val==val&&num<B.num;}
}b[maxn];
int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if (ch=='-')f=-f;ch=getchar();} 
    while(isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
    return ret*f;
}
int search(int v){
    int L=1,R=N;
    while (L<=R){
        int mid=(R-L>>1)+L;
        if (a[mid].p>=v) L=mid+1;else R=mid-1;
    }
    return R;
}
int Get(int x){return pre[x]==x?x:pre[x]=Get(pre[x]);}
bool cmp(int x,int y){return y<x;}
int main(){
    N=read(),M=read(),O=read();
    for (int i=1;i<=N;i++) a[i].cos=read(),a[i].p=read(),pre[i]=i;
    for (int i=1;i<=M;i++) b[i].val=read(),b[i].num=read();
    sort(a+1,a+N+1);sort(b+1,b+M+1);
    int tot=0;
    for (int i=1;i<=M;i++){
        int x=Get(search(b[i].num));
        if (x){
            if (b[i].val-a[x].cos<=0) continue;
            Mon[++tot]=b[i].val-a[x].cos;
            pre[x]=Get(x-1);
        }
    }
    sort(Mon+1,Mon+tot+1,cmp);
    for (int i=1;i<=min(O,tot);i++) Ans+=Mon[i];
    printf("%lld\n",Ans);
    return 0;
}