[IOI2013]robots 题解

题目链接-luogu

首先题意可以转化为(:)每个玩具有两个属性值(x_i,y_i,)弱机器人可以拿掉(x_i<A_i)的玩具(,)小机器人可以拿掉(y_i<B_i)的玩具(.)

不难想到可以二分答案(.)

考虑如何(check)是否能在(mid)分钟的时间内拿走所有的玩具(.)

首先如果只有一维(,)显然可以直接对(x_i)和(A_i)排序然后丢掉多余的机器人(,)直接比大小即可(.)

那么多加了一维就是对(x)先贪心(,)每次尽量拿走(y)更大的数字即可(.)

这个贪心很容易用一个堆来实现(.)

(O(nlog ans log n).)

代码 (:)

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &x){
	x = 0; char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
const int N = 500005,M = 100005;
struct st{ int x,y; bool operator < (const st w) const{ return x < w.x; } }p[N];
int A,B,n,a[M],b[M],ca[M],cb[M]; priority_queue<int>H;
inline bool check(int Mid){
	int i;
	for (i = 1; i <= A; ++i) ca[i] = Mid;
	for (i = 1; i <= B; ++i) cb[i] = Mid;
	int now = 1;
	while (!H.empty()) H.pop();
	for (i = 1; i <= A; ++i){
		while (now <= n && p[now].x < a[i]) H.push(p[now].y),++now;
		while (ca[i]-- && !H.empty()) H.pop();
	}
	while (now <= n) H.push(p[now].y),++now;
	for (i = B; i >= 1; --i)
		while (!H.empty() && cb[i]-- && b[i] > H.top()) H.pop();
	return H.empty();
}
int main(){
	int i;
	read(A),read(B),read(n);
	for (i = 1; i <= A; ++i) read(a[i]); sort(a+1,a+A+1);
	for (i = 1; i <= B; ++i) read(b[i]); sort(b+1,b+B+1);
	for (i = 1; i <= n; ++i) read(p[i].x),read(p[i].y); sort(p+1,p+n+1);
	int Ans = -1,L = 1,R = n,Mid;
	while (L <= R){ Mid = L+R>>1; if (check(Mid)) R = Mid-1,Ans = Mid; else L = Mid + 1; }
	cout << Ans << '
';
	return 0;
}