自动搬运

查看原文

来自洛谷，原作者为

	Mortidesperatslav 岂不日戒，玁狁孔棘。

搬运于2025-08-24 21:28:40，当前版本为作者最后更新于2024-02-05 14:03:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

脑洞题。绝世好题。

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

这也是本题的核心思路。

然后我们可以发现，如果 $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;
}

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