Keshawn_lu's Blog

浙工商OJ 6.jlh的童年1

字数统计: 458阅读时长: 2 min
2021/02/02 Share

题目简介:

jlh小时很喜欢玩弹珠,但是他的玩法有些特别。他在一条直线上放一些纸当陷阱,弹珠每次必须跳过一个陷阱(不能多也不能少),并且不掉到陷阱内,如果弹珠顺利跳过所有陷阱,就算成功了,否则就算失败。我们假设弹珠每次跳相同的距离,现在让你写一个程序帮jlh判断,到底有没有可能成功。

Input:

先输入一个T,表示有T组测试数据。每次输入一个n(n<=100),表示有n个陷阱,接下来n行,每行输入区间(l,r),表示陷阱(0<=l<=r<=50000)。

Output:

如果jlh有可能成功,输出YES,否则输出NO。

Sample Input:

1
2
3
4
5
6
7
2
2
0 1
1 2
2
0 1
1 3

Sample Output:

1
2
YES
NO

思路:

这题其实有点小错误,按照它的意思,每个陷阱是连在一起的,即当前陷阱的结尾是下一个陷阱的开头。

所以我们先将所有陷阱中的最大距离求出来,然后每次按照最大距离去跳,从而判断即可。

trap[j][0] + max_distance > trap[j + 1][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
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{

int t;
int n;

cin >> t;

for (int i = 0; i < t; i++) {

cin >> n; //n个陷阱
vector<vector<int>> trap(n);

int flag = 0;
int max_distance = 0; //陷阱间的最大距离

int begin, end;
for (int j = 0; j < n; j++) {

cin >> begin >> end; //陷阱开始,结束
max_distance = max(max_distance, end - begin);

trap[j].push_back(begin);
trap[j].push_back(end);
}

for (int j = 0; j < n - 1; j++) {

if (trap[j][0] + max_distance > trap[j + 1][0]) {

flag = 1;
break;
}
}

if (flag == 1)
cout << "NO" << endl;
else
cout << "YES" << endl;
}

}
CATALOG
  1. 1. 题目简介:
  2. 2. Input:
  3. 3. Output:
  4. 4. Sample Input:
  5. 5. Sample Output:
  6. 6. 思路:
  7. 7. 代码如下: