P4698 [CEOI2011]Hotel

liunian · 2019-07-20 08:24:00 · 题解

• 这道题维度多得我都数不过来了。

• 其实这道题，找到单调性就容易突破了。

• 很明显是贪心思想，首先排序，房间按容量从大到小排，订单按租金从大到小排，对于每一个订单，二分查找到刚好满足能住进的房间。

• 但是万一这个房间已经住人了呢? 因此想到用并查集，维护刚好满足能住进且未住人的房间编号。

• 若一个房间被一个订单占用，那么它的父亲就变成了它的编号-1，这样一定是最优的（想想为什么），然后还要注意当它的父亲为0时，不能选用。

• 每一个订单花费为b[i].x-a[res].x即订单租金减去选中的房间维修费，用一个数组存起来。

• 将花费排序，从后往前选o（最大订单数）个花费，若o<tot(花费组数)就全加，得到答案。

代码部分：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e5+5;
ll ans,icm[maxn];
int n,m,o,sum,pre[maxn],tot;
bool mark[maxn];

struct node {
    int x,y;
} a[maxn],b[maxn];

bool cmp1(node a,node b) {
    if(a.y==b.y)return a.x>b.x;
    return a.y>b.y;
}

bool cmp2(node a,node b) {
    if(a.x==b.x)return a.y>b.y;
    return a.x>b.x;
}

int find(int x) {
    return pre[x]==x?x:pre[x]=find(pre[x]);
}

int main() {
    scanf("%d%d%d",&n,&m,&o);
    for(int i=1; i<=n; i++)scanf("%d%d",&a[i].x,&a[i].y),pre[i]=i;
    for(int i=1; i<=m; i++)scanf("%d%d",&b[i].x,&b[i].y);
    sort(a+1,a+n+1,cmp1);
    sort(b+1,b+m+1,cmp2);
    for(int i=1; i<=m; i++) {
        int l=1,r=n,res=-1;
        while(l<=r) {
            int mid=l+r>>1;
            if(a[mid].y>=b[i].y)l=mid+1,res=mid;
            else r=mid-1;
        }
        if(res==-1)continue;
        if(!mark[res]) {
            if(b[i].x-a[res].x<=0)continue;
            mark[res]=1,pre[res]=res-1,icm[++tot]=b[i].x-a[res].x;
        } else {
            int fa=find(res);
            if(!fa)continue;
            if(b[i].x-a[fa].x<=0)continue;
            mark[fa]=1,pre[fa]=fa-1,icm[++tot]=b[i].x-a[fa].x;
        }
    }
    sort(icm+1,icm+tot+1);
    for(int i=tot; i>=1; i--) {
        if(sum==o)break;
        ans+=icm[i];
        sum++;
    }
    printf("%lld\n",ans);
    return 0;
}