比赛 贪心题目练习 评测结果 WWWW
题目名称 旅行家的预算 最终得分 0
用户昵称 htl 运行时间 0.012 s
代码语言 C++ 内存使用 3.31 MiB
提交时间 2025-03-22 10:13:04
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int n, m1, m2;
struct node
{
	int a;
	int b;
};
bool operator<(node a, node b)
{
	return a.b < b.b;
}
bool operator>(node a, node b)
{
	return a.b > b.b;
}
node na[100010], nb[100010];
bool cmp(node a, node b)
{
	return a.a < b.a;
}
int f(node* ab, int lon, int _n)
{
	priority_queue<node, vector<node>, greater<node> > q;
	int ans = 0;
	int ll = _n;
	for (int i = 1; i <= lon; i++)
	{
		while (!q.empty() && q.top().b <= ab[i].a)
		{
			q.pop();
			ll++;
		}
		if (ll == 0)
		{
			continue;
		}
		q.push(ab[i]);
		ll--;
		ans++;
	}
	return ans;
}

int main()
{
    freopen("lyuxing.in","r",stdin);
    freopen("lyuxing.out","w",stdout);
	cin >> n >> m1 >> m2;
	for (int i = 1; i <= m1; i++)
	{
		cin >> na[i].a >> na[i].b;
	}
	for (int i = 1; i <= m2; i++)
	{
		cin >> nb[i].a >> nb[i].b;
	}
	sort(na + 1, na + m1 + 1, cmp);
	sort(nb + 1, nb + m2 + 1, cmp);
	int ans = 0, t = 0;
	int l = 0, r = n;
	int mid1, mid2;
	while (r - l > 2)
	{
		mid1 = l + (r - l) / 3;
		mid2 = r - (r - l) / 3;
		if (f(na, m1, mid1) + f(nb, m2, n - mid1) > 
			f(na, m1, mid2) + f(nb, m2, n - mid2))
		{
			r = mid2;
		}
		else
			l = mid1;
	}
	ans = -1;
	for (int i = l; i <= r; ++i)
	{
		ans = max(f(na, m1, i) + f(nb, m2, n - i), ans);
	}
	cout << ans;
	return 0;
}