【题解】洛谷P7913 廊桥分配

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

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

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

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

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

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

  6. 对国际航班如法炮制,得到记录第 ii 个廊桥上停放过的国际航班飞机数量的数组 cnt2cnt2

  7. cnt1cnt1cnt2cnt2 进行前缀和,它们的含义变为使用 ii 个廊桥一共能停放 cntcnt 架飞机。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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;
}

【题解】洛谷P7913 廊桥分配
https://blog.ikale.io/p/70ab165d/
作者
Ikaleio
发布于
2022年9月10日
许可协议
CC-BY-SA