6 分求调,和题解对拍 30000 组无果
查看原帖
6 分求调,和题解对拍 30000 组无果
1125291
ZMQ_Ink6556楼主2025/2/5 20:11
#include<bits/stdc++.h>
using namespace std;
struct p
{
	long long c;
	int p;
}a[500005];
struct p_
{
	long long v;
	int d , r;
}b[500005];
inline bool cmp1(p l , p r)
{
	if(l.p == r.p)
	{
		return l.c > r.c;
	}
	return l.p > r.p;
}
inline bool cmp2(p_ l , p_ r)
{
	if(l.d == r.d)
	{
		return l.v > r.v;
	}
	return l.d > r.d;
}
int n , m , o , tmp = 1;
priority_queue<long long> q;
long long ans;
bool vis[500005];
int main()
{
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> o;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> a[i].c >> a[i].p;
	}
	for(int i = 1 ; i <= m ; i++)
	{
		cin >> b[i].v >> b[i].d;
	}
	sort(a + 1 , a + n + 1 , cmp1);
	sort(b + 1 , b + m + 1 , cmp2);
	for(int i = 1 ; i <= m ; i++)
	{
		while(a[tmp + 1].p >= b[i].d)
		{
			tmp++;
		}
		b[i].r = tmp;
	}
	a[0].c = a[0].p = 1000000009;
	for(int i = 1 ; i <= m ; i++)
	{
		tmp = b[i].r;
		while(vis[tmp])
		{
			tmp--;
		}
		q.push(b[i].v - a[tmp].c);
		vis[tmp] = 1;
		if(!tmp)
		{
			vis[tmp] = 0;
		}
	}
	for(int i = 1 ; i <= o ; i++)
	{
		if(q.empty())
		{
			break;
		}
		if(q.top() <= 0)
		{
			break;
		}
		ans += q.top();
		q.pop();
	}
	cout << ans;
	return 0;
}
2025/2/5 20:11
加载中...