CF1872B题解

发表于 更新于 分类于

题目大意

你在一条无限长的路上，初始坐标是 11。对于每一个陷阱 ii，会在走到坐标 did_{i} 后第 sis_{i} 秒无法进入或离开坐标 did_{i}。求你最远能去到并回到 11 的坐标。

思路

（我）看到这种题一下就想到二分答案。

实现

我们先定义一个结构体 traptrap 来存储所有陷阱，按他们的坐标升序排序：

1
2
3
4
5
6
struct trap{
	int d,s;
	bool operator <(trap b) const{
		return d<b.d;
	}
}a[102];

对于二分中 ll 和 rr 的设置，有以下两点：

  • 题目中 1≤di,si≤2001 \le d_{i},s_{i} \le 200，那么很明显我们不可能走到坐标 10001000 还安全回来。
  • 初始坐标是 11，那我们即使不动答案也是 11 。

所以设置 l←1,r←1000l \gets 1,r \gets 1000。

对于 checkcheck 函数，很明显我们可以越过陷阱 ii 最多 (si−1)÷2(s_{i}-1)\div2 格（除以二是因为要留一半时间回来），所以 checkcheck 函数是这样的：

1
2
3
4
5
6
7
bool check(int k){
	for(int i=1;i<=n&&a[i].d<=k;++i){
		if(a[i].d+(a[i].s-1)/2<k)
			return 0;
	}
	return 1;
}

完整代码：

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
#include<cstdio>
#include<algorithm>
using namespace std;
struct trap{
	int d,s;
	bool operator <(trap b) const{
		return d<b.d;
	}
}a[102];
int t,n,l,r;
bool check(int);
int main(){
	scanf("%d",&t);
	while(t--){
		for(int i=0;i<102;++i){
			a[i]={0,0};
		}//多组数据初始化
		r=1000,l=1;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d%d",&a[i].d,&a[i].s);
		}
		sort(a+1,a+n+1);
		while(r-l>1){//标准二分
			int mid=(l+r)/2;
			if(check(mid)){
				l=mid;
			}else{
				r=mid;
			}
		}
		printf("%d\n",l);
	}
}
bool check(int k){
	for(int i=1;i<=n&&a[i].d<=k;++i){
		if(a[i].d+(a[i].s-1)/2<k)
			return 0;
	}
	return 1;
}