题解：P1752 点菜

这题是一道绝世好题。
为什么咩？
因为它代码长。
因为它没有运用什么高级算法，但用低级算法组成了一道紫题。

题意转化

读完题后，我们可以发现，重复吃菜是对题目没有贡献的，所以即使没有能吃并且没有吃过的的菜，也不重复吃。
换一种讲法，就是每种菜只有一盘，问最少要吃多少天。（原本是周，以下为了方便说成天）

思路

首先，根据算法标签我们得知应该使用二分，因为算法标签天数越多越容易每种菜都吃一遍，反之越少越不容易。

现在问题就变为了如何判断 $k$ 天能否每种菜都吃一遍。

很容易发现应该用贪心。

证明贪心

我们贪的做法是：让挑剔的人在他能吃的菜中吃最贵的，穷人也是一样，从他能吃的菜中吃最不美味的。
为什么这么做呢？因为谁叫他们这么挑剔挑剔的人是没有钱的限制的，所以尽量让他吃最贵的，把便宜的留给穷人吃。穷人也是一样，吃不美味的，把美味的留给挑剔的人吃。

既是最便宜又是最美味的菜

聪明的读者可能会想到，如果一种菜既是最便宜又是最美味的，这种应该给挑剔的人吃开始给穷人吃呢？

其实要根据挑剔的人可以吃的数量还是穷人可以吃的数量确定，但是这不影响，因为我们不是让挑剔的人吃最美味的，或者让穷人吃最便宜的。

给挑剔的人还是给穷人

如果穷人所有能吃的挑剔的人也能吃，那给谁呢？

其实不影响，因为题目的目的不是给谁吃。

代码

思路讲完了，代码又该怎么实现呢（天数为 $k$）？

首先，如果 $(n-p-q)\times k \geq m$ 那么一定可以吃完，因为如果普通的人吃 $k$ 天都能吃完那算上有限制的人也一定能吃完。

if((long long)(n - cn - pn) * k >= m)//注意使用long long
	return true; 

然后，枚举挑剔的人能吃的菜，从中选出最贵给挑剔的人吃掉。
其中，选出最贵的菜可以使用优先队列（priority_queue）。

priority_queue <point> q;
int sum = 1;
for(int i = 1; i <= cn; i++)
{
	while(sum <= m && a[sum].x >= c[i])
		q.push(a[sum++]);
	for(int j = 1; j <= k && (!q.empty()); j++) q.pop(); 
}

选出剩下的菜和挑剔的人不能吃的菜放到一个数组里。

int cnt = 0;
while(!q.empty())
{
	s[++cnt] = q.top();
	q.pop();
} 
for(int i = sum; i <= m; i++)
	s[++cnt] = a[i];

按价格排序，在剩下的菜把穷人能吃的给穷人吃。

sort(s + 1, s + cnt + 1);
int top = 1;
for(int i = 1; i <= pn; i++)
{
	while(top <= cnt && s[top].y <= p[i]) q.push(s[top++]);
	for(int j = 1; j <= k && q.size(); j++) q.pop();
}

判断剩下的菜普通人能否吃完。

int res = qq.size() + cnt - top + 1;
return(res <= (n - p - q) * k);

最终代码

#include<bits/stdc++.h> I AK IOI.
using namespace std;
int n, m, cn, pn, c[50010], p[50010];
struct point{
	int x, y;
	bool operator < (point t) const
	{
		return y < t.y;
	}
}a[200010], s[200010];

bool cmp(point x, point y){
	return x.x > y.x;
}
bool check(int k)
{
	if((long long)(n - cn - pn) * k >= m)
		return true; 
	priority_queue <point> q;
	int sum = 1;
	for(int i = 1; i <= cn; i++)
	{
		while(sum <= m && a[sum].x >= c[i]) q.push(a[sum++]);
		for(int j = 1; j <= k && (!q.empty()); j++) q.pop(); 
	}
	
	int cnt = 0;
	while(!q.empty())
	{
		s[++cnt] = q.top();
		q.pop();
	} 
	for(int i = sum; i <= m; i++)
		s[++cnt] = a[i];
	sort(s + 1, s + cnt + 1);
	int top = 1;
	for(int i = 1; i <= pn; i++)
	{
		while(top <= cnt && s[top].y <= p[i]) q.push(s[top++]);
		for(int j = 1; j <= k && q.size(); j++) q.pop();
	}
	int res = q.size() + cnt - top + 1;
	return(res <= (n - cn - pn) * k);
}
int main()
{
	cin >> n >> m >> cn >> pn;
	for(int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y;
	for(int i = 1; i <= cn; i++) cin >> c[i];
	for(int i = 1; i <= pn; i++) cin >> p[i];
	
	sort(a + 1, a + m + 1, cmp);
	
	sort(c + 1, c + cn + 1, greater<int>());
	
	sort(p + 1, p + pn + 1);
	
	int l = 1, r = m, mid, ans = -1;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << ans;
	return 0;
}