25pts求条
查看原帖
25pts求条
690243
houluyu楼主2024/9/3 12:21
/*
只有当编号较小的不行的时候才用大的 

每次选前面最小的一定不劣 
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int> 
#define f first
#define s second
using namespace std;

const int M = 100005, N = 100005;
struct dat{
	int x, y;
}a1[M], a2[M];
int n, m1, m2, nei[N], wai[N], sum1, sum2, qn[N], qw[N], ans;//国内国外分配机器能有多少   国内国外滴i个能有多少  qn[i]是前i个国内廊桥能有多少 
priority_queue<pii, vector<pii>, greater<pii> > q;//小根堆,时间最小的   占用到的时间1和编号   f是最后的时间 s是第几个廊桥
priority_queue<int, vector<int>, greater<int> > fr;                
bool cmp(dat xx, dat yy)
{
	return xx.x < yy.x;
}              
signed main()      
{        
//	freopen("airport3.in", "r", stdin);                          
//	freopen("std.out", "w", stdout);           
	
    ios::sync_with_stdio(0);                  
    cin.tie(0);  
    cout.tie(0);
    cin >> n >> m1 >> m2;
    for(int i = 1; i <= m1; i ++)
    {
		cin >> a1[i].x >> a1[i].y;
	}
	for(int i = 1; i <= m2; i ++)
	{
		cin >> a2[i].x >> a2[i].y;
	}
	sort(a1 + 1, a1 + 1 + m1, cmp);
	sort(a2 + 1, a2 + 1 + m2, cmp);
	q.push({a1[1].y, 1});
	sum1 = 1;
	nei[1] = 1;
    for(int i = 2; i <= m1; i ++)
	{
		int f = 0; 
		pii t = q.top();
//		cout <<a1[i].x << ' '<<  t << endl;
		while(!q.empty() && q.top().f <= a1[i].x)
		{
			fr.push(q.top().s);
			q.pop();
		}		
		if(!fr.empty())
		{
			q.push({a1[i].y, fr.top()});
			f = fr.top();
			fr.pop();
		}
		if(!f)
		{
			sum1 ++;
			q.push({a1[i].y,sum1});
			f = sum1;
		}
		nei[f] ++;
	} 
	for(int i = 1; i <= n; i ++)
	{
		qn[i] = qn[i - 1] + nei[i]; 
//			cout << qn[i] << ' ';	
	}
	
//	cout << endl;
//	return 0;	
	
	
	while(!q.empty())q.pop();
	while(!fr.empty())q.pop();
	q.push({a2[1].y, 1});
	sum2 = 1;
	wai[1] = 1;
    for(int i = 2; i <= m2; i ++)
	{
		int f = 0; 
		while(!q.empty() && q.top().f <= a2[i].x)
		{
			fr.push(q.top().s);
			q.pop();
		}		
//			cout <<a2[i].x << ' ' <<  t.f << ' ' << t.s << ' ' << f << endl;
		if(!fr.empty())
		{
			q.push({a2[i].y, fr.top()});
			f = fr.top();
			fr.pop();
		}
		if(!f)
		{
			sum2 ++;
			q.push({a2[i].y, sum2});
			f = sum2;
		}
//		cout << f << endl;
		wai[f] ++;
	} 
	for(int i = 1; i <= n; i ++)
	{
		qw[i] = qw[i - 1] + wai[i]; 
//		cout << qw[i] << ' ';
	}
	for(int i = 0; i <= n; i ++)//给国内i个 国外n - i个 
	{
//		cout << qn[i] << ' ' << qw[n - i] << endl;
//		cout << qn[i] << ' ' << qw[n - i] << endl;
		ans = max(ans, qn[i] + qw[n - i]); 
	}
//	cout << endl;
	cout << ans;
	
    
    
    /*
	学奥赛,伊利,学习身体,心理承受,
	时间不固定,自己心里有数,争取两方面不耽误,水平
	选择自己道路,别托拉,快决定, 不能借助这个逃避文化课 
	*/
    
    
    
    
    
    
    
    
    
    
    return 0;

}
2024/9/3 12:21
加载中...