样例能够,数据全WA,求二分问题在哪儿
查看原帖
样例能够,数据全WA,求二分问题在哪儿
287412
lixiang314楼主2021/10/30 16:39
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000;
typedef long long ll;
struct T{
	ll a;
	ll b;
};
vector<ll> f11,f22,t1,t2;
T f1[maxn+5],f2[maxn+5];
ll k1[maxn+5],k2[maxn+5];
bool vis1[maxn+5],vis2[maxn+5];
bool cmp(T x,T y){
	return x.a<y.a;
}
int main(){
//	freopen("airport.in","r",stdin);
//	freopen("airport.out","w",stdout);
	f11.push_back(-1);t1.push_back(0);
	f22.push_back(-1);t2.push_back(0);
	ll n,m1,m2;
	cin>>n>>m1>>m2;
	if(n>=(m1+m2)){
		cout<<m1+m2<<endl;
		return 0;
	}
	for(int i=1;i<=m1;i++)cin>>f1[i].a>>f1[i].b;
	for(int i=1;i<=m2;i++)cin>>f2[i].a>>f2[i].b;
	sort(f1+1,f1+m1+1,cmp);
	sort(f2+1,f2+m2+1,cmp);
	for(int i=1;i<=m1;i++)f11.push_back(f1[i].a);
	for(int i=1;i<=m2;i++)f22.push_back(f2[i].a);
	for(int i=1;i<=m1&&vis1[i]==false;i++){
		vis1[i]=true;
		ll sum=1;
		ll bz=f1[i].b;
		ll num=0;
		while(true){
			num++;
			ll k=upper_bound(f11.begin(),f11.end(),bz)-f11.begin();
			if(k==f11.size())break;
			if(vis1[k]==true){
				bz=f1[k].a;
				continue;
			}
			if(vis1[k]==false){
				vis1[k]=true;
				sum++;
			}
			bz=f1[k].b;
		}
		t1.push_back(sum);
		if(num==1)break;
	}
	for(int i=1;i<=m2&&vis2[i]==false;i++){
		vis2[i]=true;
		ll sum=1;
		ll bz=f2[i].b;
		ll num=0;
		while(true){
			num++;
			ll k=upper_bound(f22.begin(),f22.end(),bz)-f22.begin();
			if(k==f22.size())break;	
			if(vis2[k]==false){
				vis2[k]=true;
				sum++;
			}
			bz=f2[k].b;
			if(vis2[k]==true)bz=f2[k].a;
		}
		t2.push_back(sum);
		if(num==1)break;
	}
	for(int i=t1.size();i<=n;i++)t1.push_back(0);
	for(int i=t2.size();i<=n;i++)t2.push_back(0);
	for(int i=1;i<=n;i++)k1[i]=k1[i-1]+t1[i];
	for(int i=1;i<=n;i++)k2[i]=k2[i-1]+t2[i];
	ll maxn=-1;
	for(int i=0;i<=n;i++)maxn=max(maxn,k1[i]+k2[n-i]);
	cout<<maxn;
	return 0;
}
2021/10/30 16:39
加载中...