【题解】洛谷P7913 廊桥分配

有一个很显然的贪心策略。

1. 将国内/国际航班分别计算。

2. 开一个数组记录 $n$ 个廊桥上次停放的飞机的离开时间，再开一个数组记录每个廊桥上停放过的飞机数量。

3. 以国内航班为例，对于每个飞机，从 $1-n$ 枚举廊桥，找到第一个能停放的（上次停放的飞机离开时间小于当前飞机进入时间），把当前的飞机塞进去，增加当前编号廊桥上停放过的飞机数量。

4. 如果找不到能用的廊桥，把这架飞机扔掉。

5. 得到记录第 $i$ 个廊桥上停放过的国内航班飞机数量的数组 $cnt1$ 。

6. 对国际航班如法炮制，得到记录第 $i$ 个廊桥上停放过的国际航班飞机数量的数组 $cnt2$ 。

7. 将 $cnt1$ 和 $cnt2$ 进行前缀和，它们的含义变为使用 $i$ 个廊桥一共能停放 $cnt$ 架飞机。

8. 暴力枚举将 $n$ 个廊桥分配给国内航班和国际航班的情况，得到 $max\{cnt1_i+cnt2_{n-i}\} (0\le i\le n)$ 即为答案。这个枚举过程是 $O(n)$ 的。

总时间复杂度 $O(n^2)$ ，以下是我的考场代码。

CCFNB! n平方的算法跑1e5竟然能得95分

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
using namespace std;
pair<int,int> a[100010],b[100010];
int n,m1,m2,id,cnt1[100010],cnt2[100010],sum1[100010],sum2[100010];
inline void calca(){
	vector<pair<int,int> > ports(n);
	for(int i=1;i<=m1;i++){
		for(int j=0;j<ports.size();j++){
			if(ports[j].second<a[i].first){
				ports[j] = a[i];
				cnt1[j+1]++;
				break;
			}
		}
	}
	for(int i=0;i<=n;i++)	sum1[i] = sum1[i-1] + cnt1[i];
}
inline void calcb(){
	vector<pair<int,int> > ports(n);
	for(int i=1;i<=m2;i++){
		for(int j=0;j<ports.size();j++){
			if(ports[j].second<b[i].first){
				ports[j] = b[i];
				cnt2[j+1]++;
				break;
			}
		}
	}
	for(int i=0;i<=n;i++)	sum2[i] = sum2[i-1] + cnt2[i];
}
int main(){
	scanf("%d %d %d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)
		scanf("%d %d",&a[i].first,&a[i].second);
	for(int i=1;i<=m2;i++)
		scanf("%d %d",&b[i].first,&b[i].second);
	sort(a+1,a+1+m1),sort(b+1,b+1+m2);
	calca(),calcb();
	int res = 0;
	for(int i=0;i<=n;i++)
		res = max(res,sum1[i]+sum2[n-i]);
	printf("%d\n",res);
	return 0;
}

观察以上代码可发现，时间复杂度的瓶颈在于calca与calcb函数中暴力找第一个可用的廊桥。

因此可用数据结构优化这个过程，这里用分块。

存储每个块块内元素的最小值 $mn_i$ ，暴力枚举找到第一个块内元素最小值小于当前飞机进入时间的块，再在块内枚举找到那个最小元素的下标。

对于修改，直接重新计算修改位置对应的块的块内最小值。

时间复杂度 $O(n \sqrt{n})$ 。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
pair<int,int> a[100010],b[100010];
int n,m1,m2,id,cnt1[100010],cnt2[100010],sum1[100010],sum2[100010];
int arr[100010],bl[100010],lb[100010],rb[100010],mn[1010],cnt;
inline void init(){
	cnt = sqrt(n);
	for(int i=1;i<=n;i++)	bl[i] = (i - 1) / cnt + 1;
	for(int i=1;i<=n;i++){
		if(!lb[bl[i]])	lb[bl[i]] = i;
		rb[bl[i]] = i;
	}
}
inline void reset(){
	for(int i=1;i<=n;i++)	arr[i] = 0;
	memset(mn,0x3f,sizeof(mn));
	for(int i=1;i<=n;i++)	mn[bl[i]] = min(mn[bl[i]],arr[i]);
}
inline int query(int val){
	int i = lb[1];
	for(;i<=n;i=rb[bl[i]]+1)
		if(mn[bl[i]]<val)	break;
	for(;i<=n;i++)
		if(arr[i]<val)	return i;
	return -1;
}
inline void adjust(int pos,int val){
	arr[pos] = val;
	mn[bl[pos]] = 0x3f3f3f3f;
	for(int i=lb[bl[pos]];i<=rb[bl[pos]];i++)	mn[bl[pos]] = min(mn[bl[pos]],arr[i]);
}
inline void calca(){
	reset();
	for(int i=1;i<=m1;i++){
		int pos = query(a[i].first);
		if(pos!=-1){
			adjust(pos,a[i].second);
			cnt1[pos]++;
		}
	}
	for(int i=0;i<=n;i++)	sum1[i] = sum1[i-1] + cnt1[i];
}
inline void calcb(){
	reset();
	for(int i=1;i<=m2;i++){
		int pos = query(b[i].first);
		if(pos!=-1){
			adjust(pos,b[i].second);
			cnt2[pos]++;
		}
	}
	for(int i=0;i<=n;i++)	sum2[i] = sum2[i-1] + cnt2[i];
}
int main(){
	scanf("%d %d %d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)
		scanf("%d %d",&a[i].first,&a[i].second);
	for(int i=1;i<=m2;i++)
		scanf("%d %d",&b[i].first,&b[i].second);
	sort(a+1,a+1+m1),sort(b+1,b+1+m2);
	init(),calca(),calcb();
	int res = 0;
	for(int i=0;i<=n;i++)
		res = max(res,sum1[i]+sum2[n-i]);
	printf("%d\n",res);
	return 0;
}