自动搬运

查看原文

来自洛谷，原作者为

	s_r_f 这里是一个只会背板和fst的蒟蒻

搬运于2025-08-24 22:15:22，当前版本为作者最后更新于2020-07-14 17:55:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

不难想到可以二分答案$.$

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

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

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

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

$O(n\log 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 << '\n';
	return 0;
}