[Acwing] 第 51 场周赛

前言

传送门 :

C.信号

题意 : 给定多个开关,每个开关可以覆盖 [ p − r + 1 , p + r − 1 ] [p-r+1,p+r-1] [p−r+1,p+r−1]的区间,询问至少需要打开多少个区间,才可以覆盖 1 − n 1-n 1−n的范围

思路 : 因为数据范围很小,我们可以在 n l o g n nlogn nlogn的时间复杂度内完成它

因此我们可以计算出每个开关管理的区间范围,然后我们跑一遍区间覆盖

但是这里因为中间不存在空隙,所以需要 r + 1 r+1 r+1

code :

void solve(){	
	cin>>n>>r;
	vector v;
	
	for(int i=1;i>x;
		if(x){
			v.pb({i-r+1,i+r-1});
		}
	}
	sort(all(v));
	

	int L = 1,R = n;

	int res = 0 ;
	
	
	for(int i = 0 ; i