Luogu7913 廊桥分配

Arahc 11.0
  2021-10-24 08:00 2021-10-24 08:00 创建   2023-03-18 08:36:12 2023-03-18 08:36:12 更新      2.4k 字  12 分钟  

题面

简化题意

nn 个廊桥分配给 A 和 B。A 有 m1m_1 个飞机 B 有 m2m_2 个飞机。每个飞机有一段区间表示停留时间。廊桥停靠先到先得，如果没有足够的廊桥则不停靠。求最多能让多少飞机停靠廊桥。

n,m1+m2≤105n,m_1+m_2\leq 10^5。

题解

退火的话只需要考虑对于一组 a1,a2a_1,a_2 求能停几个飞机。对于每一个区间 [l,r][l,r] 会对时间轴产生两个贡献：ll 位置 +1+1，rr 位置 −1-1。表示选择这个数这一段区间会多一个占用廊桥的区间。注意如果数量超过了给它分配的廊桥数，这个区间的贡献不能计算进时间轴。

设 a1a_1 是给 A 类区间的桥数，a1a_1 增加的时候，原来在 A 类不会删除的区间还是不会被删除。B 类同理。也就是说，对于一个飞机如果需要 kk 个廊桥它才能停廊桥，那我给 k+1k+1 个，它还是可以停廊桥。

若廊桥没有数量限制，求出每一个飞机需要多少廊桥才可以停。O(n)\mathcal{O}(n) 枚举给 A 类多少廊桥，给 B 类多少廊桥，得到一共多少飞机停进来，求结果最大值。

不妨画一个图，下面的区间 a,b,c,d,e,f,ga,b,c,d,e,f,g 都属于 A 类飞机对应的区间，xx 轴表示时间轴：

  1. 第一个进场的 cc 区间需要分配一个廊桥，记廊桥编号为 11。
  2. 第二个进场的 bb 区间，因为 11 号廊桥还在被 cc 占用，所以要开一个廊桥 22。
  3. 随后 ff 区间进场，虽然廊桥 22 被 bb 占用了，但是廊桥 11 的 cc 已经用完飞走了，就没必要建新廊桥了，可以直接使用廊桥 11。
  4. gg 区间进场，廊桥 1,21,2 分别被 f,bf,b 占用，所以只能再建一个廊桥 33 给 gg 用。
  5. 然后是 aa 区间，廊桥 1,31,3 被 f,gf,g 占用，但是廊桥 22 的 bb 已经走了，所以可以进廊桥 22。
  6. 轮到 ee 进场的时候，我们发现廊桥 1,21,2 都可以使用，廊桥 33 被 gg 占用。具体是选 11 还是 22，我们不妨从简而谈，选择编号更小的廊桥，方便直接通过廊桥编号求出至少几个廊桥可以让它停进来。因此我们给 ee 选择 11 号廊桥。
  7. 姗姗来迟的 dd 只有 22 号廊桥一个选择。到此所有处理结束了。

总结手玩数据思路：

  • 对于一个区间开始的时候，先判断是否所有的廊桥已经被占用。
  • 如果所有廊桥已经被占用，新开一个廊桥给它。
  • 否则找到编号最小的廊桥给它。

线段树维护各个时间轴的点上，没有被占用的廊桥编号的最小值即可。

代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=100005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,m1,m2,q1[max_n*4],q2[max_n*4];
struct plane{
    int l,r;
    inline void init(int x,int y){
        l=x,r=y;
    }
}a[max_n],b[max_n];
inline bool cmp(plane a,plane b){ // 左端点排序
    return a.l<b.l;
}

int lisan[max_n*4],cntls;

int ans,nowans,R1,R2;

int In[max_n],a1[max_n*4],a2[max_n*4],ar[max_n],br[max_n];
// a1：国内飞机的差分贡献（左端点 +1 右端点 -1）
// In：记忆化
// ar：国内每个时间点如果有飞机进来，记录其出去的时间
// a2，br 同理，是针对国际飞机的
inline int check(int in){ // O(n) 判断几个飞机停桥
	if(In[in]) return In[in]; // 记忆化
	int out=n-in,res=0,tmp=0;
	for(register int i=1;i<=R1;++i) // 因为有修改飞机贡献所以要备份
		a1[i]=q1[i];
	for(register int i=1;i<=R2;++i)
		a2[i]=q2[i];
	for(register int i=1;i<=R1;++i){// 国内
		if(a1[i]==1 && tmp<in) // 可以停进去
			++res;
		else if(a1[i]==1) // 停不进去要撤销飞机贡献
			a1[i]=a1[ar[i]]=0;
		tmp+=a1[i];
	}
	tmp=0;
	for(register int i=1;i<=R2;++i){// 国际，同理
		if(a2[i]==1 && tmp<out)
			++res;
		else if(a2[i]==1)
			a2[i]=a2[br[i]]=0;
		tmp+=a2[i];
	}
	return In[in]=res;
}

int As[max_n];
const int tim=3;
const double tem=1145.141919810,delta=0.987654321,eps=1e-15;
// 随便怎么调参都能过冥间数据
inline void findans(){ // 模拟退火
	int anss=ans,nowanss=nowans;
	double nowt=tem;
	while(nowt>eps){
		int len=1.0*nowt*n*rand()/RAND_MAX,L=nowanss-len,R=nowanss+len;
        // 找到一个左端点和右端点
		if(L>=0){
			int tmp=check(L);
			if(tmp>anss){ // 更新当前答案
				anss=tmp,
				nowanss=L;
				if(ans<anss){ // 更新全局答案
					ans=anss,
					nowans=nowanss;
				}
			}
		}
		if(R<=n){
			int tmp=check(R);
			if(tmp>anss){
				anss=tmp,
				nowanss=R;
				if(ans<anss){
					ans=anss,
					nowans=nowanss;
				}
			}
		}
		nowt*=delta;
	}
	if(ans<anss){
		ans=anss,
		nowans=nowanss;
	}
}

signed main(){
    n=read(),m1=read(),m2=read();
    for(register int i=1;i<=m1;++i){
        int l=read(),r=read();
        a[i].init(l,r);
        lisan[++cntls]=l, // lisan 是离散化
        lisan[++cntls]=r;
    }
    sort(lisan+1,lisan+1+cntls),R1=cntls;
    for(register int i=1;i<=m1;++i){
        a[i].l=lower_bound(lisan+1,lisan+1+cntls,a[i].l)-lisan;
        a[i].r=lower_bound(lisan+1,lisan+1+cntls,a[i].r)-lisan;
        q1[a[i].l]=1,q1[a[i].r]=-1; // 统计飞机贡献
        ar[a[i].l]=a[i].r;
    }
    cntls=0;
    for(register int i=1;i<=m2;++i){ // 国际部同理
        int l=read(),r=read();
        b[i].init(l,r);
        lisan[++cntls]=l,
        lisan[++cntls]=r;
    }
    sort(lisan+1,lisan+1+cntls),R2=cntls;
    for(register int i=1;i<=m2;++i){
        b[i].l=lower_bound(lisan+1,lisan+1+cntls,b[i].l)-lisan;
        b[i].r=lower_bound(lisan+1,lisan+1+cntls,b[i].r)-lisan;
        q2[b[i].l]=1,q2[b[i].r]=-1;
        br[b[i].l]=b[i].r;
    }

    sort(a+1,a+1+m1,cmp), // 别忘记 sort
    sort(b+1,b+1+m2,cmp);

	ans=check(n/2),nowans=n/2;
	while(clock()<CLOCKS_PER_SEC*0.8)
		findans();
    write(ans);
    return 0;
}
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;
const int max_n=100005,inf=2100000000;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int lisan[max_n*4],cntls,R1,R2;

int n,m1,m2;
struct plane{
    int l,r;
    inline void init(int x,int y){
        l=x,r=y;
    }
}a[max_n],b[max_n];
inline bool cmp(plane a,plane b){
    return a.l<b.l;
}

struct segment_tree{ // 下标为时间，值为可用廊桥编号最小值
	int L[max_n*8],R[max_n*8];
	int mn[max_n*8];

	#define ls(x) (x<<1)
	#define rs(x) (x<<1|1)

	inline void pushup(int x){
		mn[x]=min(mn[ls(x)],mn[rs(x)]);
	}
	inline void build(int x,int l,int r){ // 清空线段树
		L[x]=l,R[x]=r,mn[x]=inf;
		if(l==r) return;
		int mid=(l+r)>>1;
		build(ls(x),l,mid),
		build(rs(x),mid+1,r);
		pushup(x);
	}
	inline void upd(int x,int pos,int val){ // 单点赋值
		if(L[x]==pos && R[x]==pos){
			mn[x]=val;
			return;
		}
		int mid=(L[x]+R[x])>>1;
		if(pos<=mid) upd(ls(x),pos,val);
		else upd(rs(x),pos,val);
		pushup(x);
	}
	inline int ask(int x,int l,int r){ // 区间查询最小值
		if(l<=L[x] && R[x]<=r) return mn[x];
		int mid=(L[x]+R[x])>>1,res=inf;
		if(l<=mid) res=min(res,ask(ls(x),l,r));
		if(r>mid) res=min(res,ask(rs(x),l,r));
		pushup(x);
		return res;
	}
}seg;

int ls[max_n],id[max_n]; // id->廊桥编号 ls->这个廊桥的上一个使用者
int f1[max_n],f2[max_n];// f1-> A 类区间给 i 个廊桥，有 f1[i] 个飞机可以，f2 同理

inline void sol1(){ // 处理 A 类区间
	int cnt=0; // 目前有几个廊桥
	seg.build(1,1,R1);
	for(register int i=1;i<=m1;++i){
		int l=a[i].l,r=a[i].r;
		int ask=seg.ask(1,1,l);
		if(ask==inf){ // 没有没被占用的廊桥
			id[i]=++cnt,ls[cnt]=r;
			seg.upd(1,r,cnt);
		}
		else{
			id[i]=ask,seg.upd(1,ls[ask],inf); // 清空上个主人在这个廊桥的信息
			ls[ask]=r,seg.upd(1,r,ask);// 占用这个廊桥
		}
	}
	for(register int i=1;i<=m1;++i) ++f1[id[i]];
	for(register int i=1;i<=m1;++i) f1[i]+=f1[i-1];
}
inline void sol2(){ // 处理 B 类，同理
	int cnt=0;
	memset(ls,0,sizeof(ls));
	seg.build(1,1,R2);
	for(register int i=1;i<=m2;++i){
		int l=b[i].l,r=b[i].r;
		int ask=seg.ask(1,1,l);
		if(ask==inf){
			id[i]=++cnt,ls[cnt]=r;
			seg.upd(1,r,cnt);
		}
		else{
			id[i]=ask,seg.upd(1,ls[ask],inf);
			ls[ask]=r,seg.upd(1,r,ask);
		}
	}
	for(register int i=1;i<=m2;++i) ++f2[id[i]];
	for(register int i=1;i<=m2;++i)	f2[i]+=f2[i-1];
}

signed main(){
    n=read(),m1=read(),m2=read();
    for(register int i=1;i<=m1;++i){
    	int l=read(),r=read();
		a[i].init(l,r);
		lisan[++cntls]=l,lisan[++cntls]=r;
	}
	sort(lisan+1,lisan+1+cntls),R1=cntls; // 熟悉的离散化
	for(register int i=1;i<=m1;++i){
		a[i].l=lower_bound(lisan+1,lisan+1+cntls,a[i].l)-lisan;
		a[i].r=lower_bound(lisan+1,lisan+1+cntls,a[i].r)-lisan;
	}
	cntls=0;
	for(register int i=1;i<=m2;++i){
		int l=read(),r=read();
		b[i].init(l,r);
		lisan[++cntls]=l,lisan[++cntls]=r;
	}
	sort(lisan+1,lisan+1+cntls),R2=cntls;
	for(register int i=1;i<=m2;++i){
		b[i].l=lower_bound(lisan+1,lisan+1+cntls,b[i].l)-lisan;
		b[i].r=lower_bound(lisan+1,lisan+1+cntls,b[i].r)-lisan;
	}

	sort(a+1,a+1+m1,cmp),
	sort(b+1,b+1+m2,cmp); // 记得要 sort

	sol1(),sol2();
	int ans=0;
	for(register int i=0;i<=n;++i)
		ans=max(ans,f1[i]+f2[n-i]); // i 个给 A 类，n-i 个给 B 类
	write(ans);
	return 0;
}
  • 标题: Luogu7913 廊桥分配
  • 作者: Arahc
  • 创建于 : 2021-10-24 08:00:00
  • 更新于 : 2023-03-18 08:36:12
  • 链接: https://arahc.github.io/2021/10/24/【题解】Luogu7913-廊桥分配/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
Luogu7913 廊桥分配
  1. 题面
  2. 题解
  3. 代码