40分,求调
  • 板块P1752 点菜
  • 楼主__maqiyue
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/20 11:37
  • 上次更新2025/1/20 14:23:58
查看原帖
40分,求调
1049661
__maqiyue楼主2025/1/20 11:37
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n, m, cn, pn;
struct point
{
	int x, y;//美味度,价格
	bool operator<(const point& b) const
	{
		return y > b.y;
	}
}a[200010], s[200010];//s:剩余的菜
int c[200010], p[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.size(); 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]), top++;
		for (int j = 1; j <= k && q.size(); j++) q.pop();
	}
	int res = q.size() + cnt - top + 1;
	return (res <= (long long)(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 + n + 1, cmp);
	sort(c + 1, c + cn + 1, greater<int>());
	sort(p + 1, p + pn + 1);
	int l = 1, r = m, ans = -1, mid;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << ans;
	return 0;
}
2025/1/20 11:37
加载中...