题目简介:
jlh小时很喜欢玩弹珠,但是他的玩法有些特别。他在一条直线上放一些纸当陷阱,弹珠每次必须跳过一个陷阱(不能多也不能少),并且不掉到陷阱内,如果弹珠顺利跳过所有陷阱,就算成功了,否则就算失败。我们假设弹珠每次跳相同的距离,现在让你写一个程序帮jlh判断,到底有没有可能成功。
先输入一个T,表示有T组测试数据。每次输入一个n(n<=100),表示有n个陷阱,接下来n行,每行输入区间(l,r),表示陷阱(0<=l<=r<=50000)。
Output:
如果jlh有可能成功,输出YES,否则输出NO。
Sample Output:
思路:
这题其实有点小错误,按照它的意思,每个陷阱是连在一起的,即当前陷阱的结尾是下一个陷阱的开头。
所以我们先将所有陷阱中的最大距离求出来,然后每次按照最大距离去跳,从而判断即可。
即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; 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; }
}
|