P1752 点菜

· · 题解

题意

有 n 个人，每个人每周至多选一道菜吃掉，求吃完 m 道菜的最小时间或无解。

这 m 道菜有美味值和价格两个参数，n 个人中 p 个人只能吃美味值大于等于一定值的菜，q 个人只能吃价格小于等于一定值的菜，其余人没有限制。

解法

可以发现如果 x 周能吃完则 x + 1 周也能吃完；如果 x 周吃不完则 x - 1 周也吃不完，说明答案具有单调性。于是考虑二分答案，check 的部分则贪心检查。

根据题意，一个可行的贪心方案是：总是让有限制的人群优先选择菜，且限制宽松的人总是吃掉条件更苛刻的（例如更贵的、更难吃的）菜，从而让限制较大的人产生更大的贡献。

这里我们选择优先考虑挑剔的 p 个人。设第 i 个挑剔的人的美味值下限为 P_i，第 j 个贫穷的人的价格上限为 Q_j；第 k 道菜的美味值为 A_k，价格为 B_k。

先将挑剔的人的美味值下限 P 从大到小排序，将 m 道菜按照美味值从大到小排序。对于第 k 道菜，如果第 i 个挑剔的人能接受这道菜，则把这道菜加入到一个待处理菜的队列里（原因后面会讲），然后考虑第 (k+1) 道菜；如果不能接受，则让他尽可能吃光这个队列里的菜，然后考虑第 (i + 1) 个人。

做法原因：因为对原数组进行过排序，第 i 个人不能接受的菜，前 (i-1) 个人一定无法接受；同理第 i 个人能接受的菜，后 (p-i) 个人一定可以接受。对于第 i 个人，当前队列里的菜都是他能吃的，后面的人也能吃。这就保证了每个人在限制内吃到最多的菜，对答案贡献最大。

肯定有更简洁的方法，这种方法只是写起来清晰一些o.O

考虑完所有的菜后，如果还有挑剔的人没有被考虑，此时队列里的菜他们肯定都能吃，所以让他们去尽可能吃光队列里的菜。最后队列里剩下的菜交给穷人和普通人处理。

将贫穷的 q 个人的价格上限 Q 也从大到小排序。这里因为是上限，第 j 个人能吃的菜，前 (j-1) 个人都能吃；反之则后 (q-i) 个人一定吃不起。对于第 j 个贫穷的人，如果他不能接受队列中第 k 贵的菜，而前面的人又都吃了尽可能多的才，则说明这道菜只能由普通人吃，将其弹出并记录，然后考虑队列中第 (k+1) 贵的菜；否则当前队列比第 k 贵的菜便宜的菜他都吃得起，就让他尽可能去吃这些菜，然后考虑第 (j+1) 个贫穷的人。

考虑完所有贫穷的人后，队列里剩下的菜和被记录的菜由剩下的 (n-p-q) 个普通人解决。最后判断普通人能否吃完即可。

实现

考虑挑剔的人时可以用两个指针，分别记录当前考虑到了哪道菜、哪个人，待处理队列使用优先队列（按照价格从大到小）。假设当前二分的答案为 week，则每个人最多可以吃掉 week 道菜。最后可以用一个变量 tot 记录有几道菜没被吃而被弹出（被记录的菜），设最终优先队列里还剩下 siz 道菜，如果 tot+siz\leq week(n-p-q)，则当前答案 week 合法。

设有 m 道菜（m\leq2\times10^5），二分答案 O(\log m)，贪心部分 O(m\log m)，总时间复杂度 O(m\log^2m)。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 50005,maxm = 2e5 + 5;
ll P[maxn],Q[maxn]; int q,n,m,p,ans = -1; pair<ll,ll> M[maxm];
bool check(int week) {
    int j = 1,tot = 0; priority_queue<int> pq;
    for (int i = 1;i <= m;i ++) {
        for (;j <= p && P[j] > M[i].first;j ++)
            for (int k = 1;k <= week;k ++)
                if (pq.empty()) break;
                else pq.pop();
        pq.push(M[i].second);
    }
    for (;j <= p;j ++)
        for (int k = 1;k <= week;k ++)
            if (pq.empty()) break;
            else pq.pop();
    for (int i = 1;i <= q;i ++) {
        while (!pq.empty() && Q[i] < pq.top())
            pq.pop(), tot ++;
        for (int k = 1;k <= week;k ++)
            if (pq.empty()) break;
            else pq.pop();
    }
    return (n - p - q) * week >= tot + pq.size();
}
int main() {
    scanf("%d%d%d%d",&n,&m,&p,&q);
    for (int i = 1;i <= m;i ++)
        scanf("%lld%lld",&M[i].first,&M[i].second);
    for (int i = 1;i <= p;i ++) scanf("%lld",&P[i]);
    for (int i = 1;i <= q;i ++) scanf("%lld",&Q[i]);
    sort(M + 1,M + m + 1); reverse(M + 1,M + m + 1);
    sort(P + 1,P + p + 1); reverse(P + 1,P + p + 1);
    sort(Q + 1,Q + q + 1); reverse(Q + 1,Q + q + 1);
    int l = 1,r = m,mid;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d",ans);
    return 0;
}