0分求助
查看原帖
0分求助
297831
idgg007楼主2021/10/24 00:14
#include<cstdio>
#include<algorithm>
using namespace std;
int sumBirdge, sumPlane_1, sumPlane_2;
int arrive_1[100005];
int leave_1[100005];
int arrive_2[100005];
int leave_2[100005];
int subscriptSort[100005];//下标排序进入时间
int usedSet[100005];	//差分记录在当前独立阶段内廊桥数所对应的使用情况
int useRemember[100005];//多少个廊道时可用
int nxt[100005];//next
int maxFree = 1;
int F_1[105];
int F_2[105];
bool Cmp_1(int a, int b) {				//以到的顺序排
	return arrive_1[a] < arrive_1[b];
}
bool Cmp_2(int a, int b) {
	return arrive_2[a] < arrive_2[b];
}
int LowBit(int n) {
	return n & (-n);
}
void AddData(int x, int n) {
	for (int i = x; i <= sumBirdge; i += LowBit(i))
		usedSet[i] += n;
}
int SumData(int x) {
	int Sum = 0;
	for (int i = x; i > 0; i -= LowBit(i))
		Sum += usedSet[i];
	return Sum;
}
int main() {
	scanf("%d%d%d", &sumBirdge, &sumPlane_1, &sumPlane_2);
	nxt[0] = 1;
	for (int i = 1; i <= sumPlane_1; i++) {
		nxt[i] = i + 1;
		subscriptSort[i] = i;
		scanf("%d%d", &arrive_1[i], &leave_1[i]);
	}
	sort(subscriptSort + 1, subscriptSort + 1 + sumPlane_1, Cmp_1);
	for (int i = 1; i <= sumPlane_1; i++) {
		int Subtime = subscriptSort[i];
		for (int j = 0; nxt[j] < i;) {				//链表山飞姬
			if (leave_1[nxt[j]] < arrive_1[Subtime]) {
				AddData(useRemember[nxt[j]], -1);	//退
				nxt[j] = nxt[nxt[j]];
			} else {
				j = nxt[j];
			}
		}
		while (maxFree > 0 && SumData(maxFree) < maxFree)
			maxFree--;
		maxFree++;									//最近空位
		AddData(maxFree, 1);
		useRemember[Subtime] = maxFree;				//记录在第几个廊桥,便于闪飞姬
		for (int j = maxFree; j <= sumBirdge; j++)	//当廊桥数大于maxFree时该飞姬场可以多容下一个飞姬
			F_1[j]++;
		while (maxFree < sumBirdge && SumData(maxFree) == maxFree)
			maxFree++;
	}
	for (int i = 0; i <= sumBirdge; i++) {
		useRemember[i] = 0;
		usedSet[i] = 0;
	}
	maxFree = 1;
	nxt[0]=1;
	for (int i = 1; i <= sumPlane_2; i++) {
		nxt[i] = i + 1;
		subscriptSort[i] = i;
		scanf("%d%d", &arrive_2[i], &leave_2[i]);
	}
	sort(subscriptSort + 1, subscriptSort + 1 + sumPlane_2,Cmp_2);
	for (int i = 1; i <= sumPlane_2; i++) {
		int Subtime = subscriptSort[i];
		for (int j = 0; nxt[j] < i;) {				//链表山飞姬
			if (leave_2[nxt[j]] < arrive_2[Subtime]) {
				AddData(useRemember[nxt[j]], -1);
				nxt[j] = nxt[nxt[j]];
			} else {
				j = nxt[j];
			}
		}
		while (maxFree > 0 && SumData(maxFree) < maxFree)
			maxFree--;
		maxFree++;
		AddData(maxFree, 1);
		useRemember[Subtime] = maxFree;
		for (int j = maxFree; j <= sumBirdge; j++)
			F_2[j]++;
		while (maxFree < sumBirdge && SumData(maxFree) == maxFree)
			maxFree++;
	}
	int Ans=0;
	for(int i=0;i<=min(sumPlane_1,sumBirdge);i++){
		Ans=max(Ans,F_1[i]+F_2[sumBirdge-i]);
	}
	printf("%d",Ans);
	return 0;
}
2021/10/24 00:14
加载中...