P1752 点菜 题解

· · 题解

P1752 点菜 题解

upd on 2024/7/16：忘写时间复杂度了，补一下。

题面大意

传送门。

解题思路

注意到答案具备单调性。

如果花费 x 周能点完所有的菜，那么花费 x+1 周也一定可以，这是显然的。

考虑对花费的周数 x 二分，其下界为 1，上界为 m（如果一周只点一道菜，最多只有 m 周），在这个范围内没有合法答案即为无解。

接下来要对 x 进行 check。

注意到这个时间限制可以转化为点菜的限制，所以下文默认 x 为每个人点菜的数量上限。

我们采取贪心的策略，让每个人都尽可能吃完他能吃的菜，且每个人吃的都不同（相同没有意义），判断最后是否能吃完。

依题意，按可以将客人分类按顺序讨论：

  1. 想吃好的人。
  2. 穷人。
  3. 正常人。

对于想吃好的人，先将菜品按美味度降序排序，再将每个人的下限按降序排序，将菜品不断甩进一个大根堆（以价格为值），每个人从堆里拿菜，直到拿 x 份或者堆空。

考虑证明其正确性：

按下限降序排序，使得前面的人选的菜，后面的人都能选，同时后面的人选的前面的人不一定能选，所以改变此方案一定不优。

容易发现此方案在只考虑想吃好的人时显然成立。

接下来讨论穷人。

对穷人，我们按每个人的价格上限升序排序，并对之前选剩的菜按价格升序排序，每个人按顺序那菜，直到拿满 x 份或者无菜可拿。

与讨论想吃好的人的证明同理，改变此方案一定不优。

最后，计算正常人能点的最大菜数，如果大于等于剩菜数，x 可以是合法答案，否则不是。

现在要将三部分的方案合起来，判断是否还是最优。

注意到想吃好的人已经将较贵的部分挑走了，所以无论是去补充没拿完的穷人还是和穷人交换，或者给正常人，都无法更优，所以我们已将想吃好的人和穷人的拿菜数最大化了。

同样，正常人的吃菜数也被最小化了，也是最优。

综上所述，我们证明了三个贪心的最优方案合起来是最优的。

所以，对 x 的 check 是正确的（拿菜数最大化还是拿不完，就是不成立，否则成立）。

按上述思路编写代码即可。

时间复杂度约为 O(m\log^2m)，可以通过本题。

代码难度至少严格弱于 P1084。

参考代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
const int N=5e5+10;
struct ccf{
    int qul,num,cont;
    friend bool operator<(ccf pre,ccf nxt){
        return pre.num<nxt.num;
    }
}dish1[N],dish2[N];
priority_queue<ccf> Q;
inline bool cmp1(ccf pre,ccf nxt){
    return pre.qul>nxt.qul;
}
inline bool cmp2(ccf pre,ccf nxt){
    return pre.num<nxt.num;
}
inline bool cmp3(int pre,int nxt){
    return pre>nxt;
}
inline bool cmp4(int pre,int nxt){
    return pre<nxt;
}
int n,m,p,q,ans=-1;
int lim1[N],lim2[N],cont[N];
bool vst[N];
inline bool check(int x){
    memset(vst,0,sizeof(vst));
    while(!Q.empty()) Q.pop();
    int i,j,t=1,tmp=x;
    for(i=1;i<=p;i++){
        for(j=t;j<=m;j++){
            if(dish1[j].qul>=lim1[i]){
                Q.push(dish1[j]);
            }else{
                break;
            }
        }
        t=j;
        tmp=x;
        while(!Q.empty()&&tmp>0){
            vst[Q.top().cont]=true;
            Q.pop();
            tmp--;
        }
    }
    int cnt1=0;
    for(i=1;i<=m;i++){
        if(!vst[dish1[i].cont]) dish2[++cnt1]=dish1[i];
    }
    sort(dish2+1,dish2+cnt1+1,cmp2);
    tmp=x;j=1;
    for(i=1;i<=cnt1;i++){
        if(dish2[i].num>lim2[j]||!tmp){
            tmp=x;
            j++;
        }
        if(j>q) break;
        vst[dish2[i].cont]=true;
        tmp--;
    }
    int cnt2=0;
    for(int i=1;i<=m;i++){
        if(!vst[i]) cnt2++;
    }
    if((n-p-q)*x>=cnt2) return true;
    else return false;
}
inline void read(int &x) {
    x=0;int f=1;
    char s=getchar();
    for(;s<'0'||s>'9';s=getchar()) f=s=='-'?-f:f;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    x*=f;
}
signed main(){
    dish1[0].cont=-1;
    ios::sync_with_stdio(false);
    read(n);read(m);read(p);read(q);
    for(int i=1;i<=m;i++){
        read(dish1[i].qul);read(dish1[i].num); 
        dish1[i].cont=i;
    }
    sort(dish1+1,dish1+m+1,cmp1);
    for(int i=1;i<=p;i++){
        read(lim1[i]);
    }
    sort(lim1+1,lim1+p+1,cmp3);
    for(int i=1;i<=q;i++){
        read(lim2[i]);
    }
    sort(lim2+1,lim2+q+1,cmp4);
    int ll=1,rr=m;
    while(ll<=rr){
        int mid=(ll+rr)/2;
        if(check(mid)){
            ans=mid;
            rr=mid-1;
        }else{
            ll=mid+1;
        }
    }
    cout<<ans;
    return 0;
}

本代码可以通过洛谷评测。

Written by toolong114514 on 2024/7/15.