题解 P5894 【[IOI2013]robots 机器人】

· · 题解

首先题意可以转化为:每个玩具有两个属性值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;
}