求助,样例1&2能过,3过不了
查看原帖
求助,样例1&2能过,3过不了
393407
Tommy_Keen楼主2021/10/26 18:13
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,mfir,msec,totf,tots,suma[N],sumb[N];

struct node {
	int l,r,id;
	bool operator < (const node &k) const {
		if(l != k.l) return l < k.l;
		else return r < k.r;
	}
} a[N],b[N];

struct item {
	int li,ri,cnt,id;
	item(){}
	item(int a,int b,int c,int d) {
		li = a; ri = b; cnt = c; id = d;
	}
	bool operator < (const item &k) const {
		return ri > k.ri;
	}
};
priority_queue <item> q;

struct now {
	int id,val;
	bool operator < (const now &k) const {
		return id < k.id;
	}
} A[N],B[N];

int main() {
	freopen("airport.in","r",stdin);
	freopen("airport.out","w",stdout);
	scanf("%d%d%d",&n,&mfir,&msec);
	for(int i = 1; i <= mfir; ++i)
		scanf("%d%d",&a[i].l,&a[i].r);
	sort(a+1,a+mfir+1);
	for(int i = 1; i <= mfir; ++i) a[i].id = i;
	
	q.push(item(a[1].l,a[1].r,1,1));
	for(int i = 2; i <= mfir; ++i) {
		item k = q.top(); 
		if(k.ri < a[i].l) {
			q.pop();
			q.push(item(k.li,a[i].r,k.cnt+1,k.id));
		} else {
			q.push(item(a[i].l,a[i].r,1,a[i].id));
		}
	}
	
	while(!q.empty()) {
		item k = q.top(); q.pop();
		A[++totf].val = k.cnt;
		A[totf].id = k.id;
	}
	sort(A+1,A+totf+1);
	
	while(!q.empty()) q.pop();
	
	for(int i = 1; i <= msec; ++i)
		scanf("%d%d",&b[i].l,&b[i].r);
	sort(b+1,b+msec+1);
	for(int i = 1; i <= msec; ++i) b[i].id = i;
	
	q.push(item(b[1].l,b[1].r,1,1));
	for(int i = 2; i <= msec; ++i) {
		item k = q.top();
		if(k.ri < b[i].l) {
			q.pop();
			q.push(item(k.li,b[i].r,k.cnt+1,k.id));
		} else {
			q.push(item(b[i].l,b[i].r,1,b[i].id));
		}
	}
	
	while(!q.empty()) {
		item k = q.top(); q.pop();
		B[++tots].val = k.cnt;
		B[tots].id = k.id;
	}
	sort(B+1,B+tots+1);
	
	for(int i = 1; i <= n; ++i) {
		suma[i] = suma[i-1] + A[i].val;
		sumb[i] = sumb[i-1] + B[i].val;
	}
	
	int ans = -1;
	for(int i = 0; i <= n; ++i)
		ans = max(ans,suma[i]+sumb[n-i]);
	printf("%d\n",ans);
	
	return 0;
}
2021/10/26 18:13
加载中...