还有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;
}
思路:分组,贪心