求助部分分思路
查看原帖
求助部分分思路
690301
Liwier楼主2022/10/1 18:52

直接模拟,为什么有些点会WA

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int ma[100086];
int mb[100086];
struct note{
	int l,r;
}a[100086],b[100086];
bool cmp(note x,note y){	
	return x.l<y.l;
}
priority_queue<int,vector<int>,greater<int> > q,q1;
void p1(){ 
	for(int i =1 ;i<=n;i++){
		//枚举分配的个数
		int sum = 0;
		q.push(0x3f3f3f3f);
		int size = 0;
		for(int j= 1;j<=m;j++){
			int l = a[j].l;
			int r = a[j].r;
//			cout<<q.top()<<endl;
			while(q.top()<l&&!q.empty()){
				q.pop();
				size--; 
			}
			if(size<i){
				sum++;
				size++;
				q.push(r);
			}
		} 
		while(!q.empty()){
			q.pop();
		}
//		cout<<endl;
		ma[i] = sum;
	}
}
void p2(){
	for(int i =1 ;i<=n;i++){
		//枚举分配的个数
		int sum = 0;
		q1.push(0x3f3f3f3f);
		int size = 0;
		for(int j= 1;j<=m;j++){
			int l = b[j].l;
			int r = b[j].r;
//			cout<<q1.top()<<endl;
			while(q1.top()<l&&!q1.empty()){
				q1.pop();
				size--; 
			}
			if(size<i){
				sum++;
				size++;
				q1.push(r);
			}
		} 
		while(!q1.empty()){
			q1.pop();
		}
		mb[i] = sum;
	}
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i = 1;i<=m;i++){
		int t1,t2;
		scanf("%lld%lld",&t1,&t2);
		a[i].l = t1;
		a[i].r = t2;
	}
	sort(a+1,a+1+m,cmp);
	for(int i = 1;i<=k;i++){
		int t1,t2;
		scanf("%lld%lld",&t1,&t2);
		b[i].l = t1;
		b[i].r = t2;
	}
	sort(b+1,b+1+k,cmp);
	p1();
//	cout<<endl;
	p2();
	int maxn = 0;
//	cout<<endl;
	for(int i =0;i<=n;i++){
//		cout<<ma[i]<<mb[i]<<endl;
		maxn = max(maxn,ma[i]+mb[(n-i)]);
	}
	cout<<maxn<<endl;
	return 0;
}
2022/10/1 18:52
加载中...