30pts WA
查看原帖
30pts WA
136939
tanghairong楼主2022/10/23 15:21

还有TLE的,是算法问题

但是不知道为什么会WA

code:

#include<iostream>
#include<algorithm>
using namespace std;
struct air{
	int x,y;
}a[100005],b[100005];
bool cmp(air u,air v){
	return u.x<v.x;
}
struct node{
	int num,maxn;
}ga[100005],gb[100005];
bool cmp2(node a,node b){
	return a.num>b.num;
}
int prea[100005],preb[100005];
int main(){
	int n,m1,m2;
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++)cin>>a[i].x>>a[i].y;
	for(int i=1;i<=m2;i++)cin>>b[i].x>>b[i].y;
	sort(a+1,a+1+m1,cmp);
	sort(b+1,b+1+m2,cmp);
	int tot1=0;
	for(int i=1;i<=m1;i++){
		int minn=0,pos=0;
		for(int j=1;j<=tot1;j++){
			if(ga[j].maxn<a[i].x){
				if(minn<ga[j].num){
					minn=ga[j].num;
					pos=j;
				}
			}
		}
		if(pos!=0){
			ga[pos].num++;
			ga[pos].maxn=a[i].y;
		}
		else{
			ga[++tot1].num=1;
			ga[tot1].maxn=a[i].y;
			pos=tot1;
		}
	}
	for(int i=1;i<=tot1;i++)prea[i]=prea[i-1]+ga[i].num;
	for(int i=tot1+1;i<=n;i++)prea[i]=prea[i-1];
	int tot2=0;
	for(int i=1;i<=m2;i++){
		int minn=0,pos=0;
		for(int j=1;j<=tot2;j++){
			if(gb[j].maxn<b[i].x){
				if(minn<gb[j].num){
					minn=gb[j].num;
					pos=j;
				}
			}
		}
		if(pos!=0){
			gb[pos].num++;
			gb[pos].maxn=b[i].y;
		}
		else{
			gb[++tot2].num=1;
			gb[tot2].maxn=b[i].y;
			pos=tot2;
		}
	}
	for(int i=1;i<=tot2;i++)preb[i]=preb[i-1]+gb[i].num;
	for(int i=tot2+1;i<=n;i++)preb[i]=preb[i-1];
	int ans=0;
	for(int i=0;i<=n;i++)ans=max(ans,prea[i]+preb[n-i]);
	cout<<ans;
	return 0;
}

思路:分组,贪心

2022/10/23 15:21
加载中...