自动搬运

查看原文

来自洛谷，原作者为

	liunian 不破天道，不回头

搬运于2025-08-24 22:02:43，当前版本为作者最后更新于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;
}