P1752题解

· · 题解

脑洞题。绝世好题。

首先，我们经过分析可以得出贪心策略：让挑剔的人选美味的，让贫穷的人点价廉的。

这也是本题的核心思路。

然后我们可以发现，如果 k 周可以点完所有菜，那么 k+1 周也能点完所有菜。

根据数学归纳法，推出：如果 k 周可以点完所有菜，那么若 n>k，n 周一定能点完所有菜。

看起来上面的性质都非常简单，但实际上这些是解决这道题目的关键。

我们推出来了，如果 k 天可以点完所有菜，那么若 n>k，n 天一定能点完所有菜。那么我们二分查找最小的 k，不就可以解决了吗？

二分的板子看这篇题解的人应该都会。二分都不会还做什么紫题关键在于判断函数怎么写。

首先，如果除去这些贫穷的人和挑剔的人，其他人都已经可以把菜选完了，那当然能把菜都选一遍。

然后我们进行贪心，即让挑剔的人选美味的，让贫穷的人点价廉的：

先把菜按照美味度排序。放到一个大根堆里，然后枚举挑剔的人，注意先把这些人喜欢的美味度按从大到小排。枚举过程很简单，开一个大根堆（推荐用 priority_queue），把每个挑剔的人喜欢的菜放进堆里，放完之后弹出直到堆空了或者是已经弹出了 k（当前二分校验的值）个元素。

因为挑剔的人从大到小排，在堆里的菜一定是让下一个人满意的。

这样挑剔的人就解决了。

剩下贫穷的人同理，把没取完的菜放入一个数组，按价格从小到大排序，然后放到任意队列里（当然为了思路更清晰，可以另开一个小根堆进行如上操作）。

最后算一算有多少道菜没取完。判断一下剩下的人能不能把这些菜点完。

然后，这道题就轻松地解决了！

#include<bits/stdc++.h>
using namespace std;
int n,m,p,q,b[114514<<2],c[114514<<2];
struct node{
    int x,y;
    bool operator<(node b)const{
        return this->y < b.y;
    }
}a[114514<<2],pp[114514<<2];
priority_queue<node>qq;
bool cmp(node x,node y){
    return x.x>y.x;
}
bool check(int k){
    if((long long)(n-p-q)*k>=m)return 1;//不需要挑剔和贫穷的人就可以取完
    while(qq.size())qq.pop();//多测清空，因为函数最后直接加上 size 了，下一次调用不清空会出错
    int top=1;
    for(int i=1;i<=p;i++) {
        while(top<=m&&a[top].x>=b[i])qq.push(a[top++]);
        for(int j=1;j<=k&&qq.size();j++)qq.pop(); 
    }//枚举挑剔的人
    int cnt=0;
    while(qq.size()){
        pp[++cnt]=qq.top();
        qq.pop();
    } 
    for(int i=top;i<=m;i++)pp[++cnt]=a[i];
    sort(pp+1,pp+cnt+1);//存入数组，按价格升序排序
    top=1;
    for(int i=1;i<=q;i++) {
        while(top<=cnt&&pp[top].y<=c[i])qq.push(pp[top++]);
        for(int j=1;j<=k&&qq.size();j++)qq.pop();
    }//枚举贫穷的人
    int res=qq.size()+cnt-top+1;
    return(res<=(n-p-q)*k);//判断剩下的人能不能取完
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>p>>q;
    for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y;
    for(int i=1;i<=p;i++)cin>>b[i];
    for(int i=1;i<=q;i++)cin>>c[i];
    sort(b+1,b+p+1);
    reverse(b+1,b+p+1);
    sort(c+1,c+q+1);
    sort(a+1,a+m+1,cmp);//全部排序
    int l=1,r=m,ans=-1;//设为 -1 可以直接判无解
    while(l<=r){//二分板子
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
}

题目出的真好，我开始感觉没有头绪，但细细拆分就变成了一道不难的题目，赞美伟大出题人！