夏晓光(loveJY)的博客

"当苦夏簌簌扑着扇，听过最后一声蝉"

蛮不错的贪心,不过灰题真的香

首先为啥具有二分性呢?因为如果我们k秒可以完成那么k+1秒也一定可以完成

然后我们就可以考虑二分一个ans,然后题目中的限制可以建图跑网络流,然后一看数据范围直接放弃

所以网络流不过就是贪心,因为只有两维我们能很简单的贪一下qwq

对于弱机器人,我们把玩具按照重量排序,然后每个机器人尽可能拿能拿的体积大的,并且机器人从小到大去选择,可以拿堆维护

剩下的玩具如果有小机器人拿不了的就完蛋

看上去很简单,但是要小心我们堆里存的东西一定是当前可以拿的...

吐槽一下神翻译小机器人和弱机器人让我笑好久

以及特判一些情况/xyx

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
const int MAXN = 1e6 + 7;
using namespace std;
int n, A, B, ans = -1;
int a[MAXN], b[MAXN];
struct rec {
	int w, s;
	bool operator<(const rec &x) {
		if(w == x.w)return s < x.s;
		return w < x.w;
	}
} t[MAXN];

priority_queue<int> heap;
inline int chk(int x) {
	int l = 1, j = 1;
	while(!heap.empty())heap.pop();
	for(int i = 1; i <= n; ++i) {
		if(l > A) {
			heap.push(t[i].s);
			continue;
		}
		if(a[l] > t[i].w) {
			heap.push(t[i].s);
		} else {
			while(a[l] <= t[i].w && l <= A) {
				j = 1;
				while(j <= x && !heap.empty()) {
					++j;
					heap.pop();
				}
				++l;
			}
			heap.push(t[i].s);
		}
	}
	for(int i = l; i <= A; ++i) {
		j = 1;
		while(j <= x && !heap.empty()) {
			++j;
			heap.pop();
		}
	}
    //特判有的强机器人能拿光所有的
	for(int i = B; i >= 1; --i) {
		j = 1;
		while(j <= x && !heap.empty()) {
			++j;
			l = heap.top();
			if(l >= b[i])return 0;
			heap.pop();
		}
		if(heap.empty())break;
	}
	if(!heap.empty())return 0;
	//还有没空的
	return 1;
}

int main() {
	scanf("%d%d%d", &A, &B, &n);
	for(int i = 1; i <= A; ++i)scanf("%d", &a[i]);
	sort(a + 1, a + A + 1);
	for(int i = 1; i <= B; ++i)scanf("%d", &b[i]);
	sort(b + 1, b + B + 1);
	for(int i = 1; i <= n; ++i)scanf("%d%d", &t[i].w, &t[i].s);
	sort(t + 1, t + n + 1);
	int L = 1, R = n, mid;
	while(L <= R) {
		mid = (L + R) >> 1;
		if(chk(mid)) {
			ans = mid;
			R = mid - 1;
		} else {
			L = mid + 1;
		}
	}
	printf("%d\n", ans);
	return 0;
}