题目描述

$Marita$ 的弟弟把玩具扔在客厅地板上，乱七八糟。庆幸的是，$Marita$ 设计了一种特殊的机器人可以收拾玩具。 不过，她需要确定哪个机器人去拣起哪个玩具。

一共有$T$个玩具,整数$W[i]$表示这个玩具的重量，整数$S[i]$表示这个玩具的体积。机器人有两种，分别是：弱机器人和小机器人。

• 有 $A$ 个弱机器人。每个弱机器人有一个重量限制 $X[i]$，它只能拿起重量严格小于 $X[i]$ 的玩具，与玩具的体积大小没关系。
• 有 $B$ 个小机器人。每个小机器人有一个体积限制 $Y[i]$，它只能拿起体积严格小于 $Y[i]$ 的玩具，与玩具的重量大小没有关系。

$Marita$ 的每个机器人用 $1$ 分钟将一个玩具拿走放好。不同的机器人可以同时拿走并放好不同的玩具。

你的任务是确定 $Marita$ 的机器人是否可以将所有的玩具都收拾好，如果是，那么最少用多少时间可以收拾好。

思路

过于amazine……这道题目我和题解打法都不一样……

我的思路是先将玩具按照体积排序，机器人都按照搬运能力(体积重量)升序排序。然后二分答案，用upper_bound查找并且让第一个能拿重量大于当前玩具重量的弱机器人拿(因为这样能先把体积大的取走)，若当前弱机器人拿了会导致时间超标就给下一个（下一个超标就给下下一个，用并查集或者线段树维护未超标的位置，不用的话暴力while只有$72$，会TLE）。然后剩下的全给小机器人拿，不过upper_bound查询的是能拿体积大于当前未被弱机器人拿走玩具体积的小机器人，然后和弱机器人一样操作，用并查集或者线段树维护位置。最后看看能不能把所有玩具全部拿走，二分出结果即可。

代码

#include<bits/stdc++.h>
#define Maxn 2000005
using namespace std;
inline void read(int &x)
{
	int f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
struct robot{int w,v;bool vis;}p[Maxn];
int A,B,T,X[Maxn],Y[Maxn],l=1,r=1000000,ans,robot_time[Maxn],fa[Maxn];
inline int getfa(int x){if (x==fa[x]) return x;return fa[x]=getfa(fa[x]);}
bool cmp(robot a,robot b){return a.v>b.v;}
inline bool check(int Tim)
{
	int cnt=0;
	for (int i=1;i<=T;i++) p[i].vis=0;
	for (int i=1;i<=A;i++) fa[i]=i; 
	memset(robot_time,0,sizeof(robot_time));
	for (int i=1;i<=T;i++)
	{
		int x=upper_bound(X+1,X+A+1,p[i].w)-X;if (x>A) continue;
		if (robot_time[getfa(x)]<Tim) robot_time[getfa(x)]++,cnt++,p[i].vis=1;
		if (robot_time[getfa(x)]==Tim&&getfa(x)!=A) fa[getfa(x)]=getfa(getfa(x)+1);
	}
	memset(robot_time,0,sizeof(robot_time));
	for (int i=1;i<=B;i++) fa[i]=i; 
	for (int i=1;i<=T;i++)
	{
		if (p[i].vis==1) continue;
		int x=upper_bound(Y+1,Y+B+1,p[i].v)-Y;if (x>B) continue;
		if (robot_time[getfa(x)]<Tim) robot_time[getfa(x)]++,cnt++;
		if (robot_time[getfa(x)]==Tim&&getfa(x)!=B) fa[getfa(x)]=getfa(getfa(x)+1);
	}
	return cnt==T;
}
int main()
{
	read(A),read(B),read(T);
	for (int i=1;i<=A;i++) read(X[i]);
	for (int i=1;i<=B;i++) read(Y[i]);
	for (int i=1;i<=T;i++) read(p[i].w),read(p[i].v);
	sort(p+1,p+T+1,cmp);
	sort(X+1,X+A+1);
	sort(Y+1,Y+B+1);
	while (l<=r)
	{
		int mid=l+r>>1;
		if (check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	if (ans==0) puts("-1");else cout<<ans<<endl;
	return 0;
}