题目描述
$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;
}