BZOJ3248 [ioi2013]robots

题目描述

$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;
} 
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇