蓝桥杯练习题F

来源:http://oj.mofriend.net/problem.php?cid=1203&pid=3

来源:http://oj.mofriend.net/problem.php?cid=1203&pid=5

题目描述
马耘是一家上市公司的董事长。10 月1 号是马耘最繁忙的一天,因为这一天有n 家商铺开张,而马耘必须在每家商铺的开业典礼上剪彩,马耘出席时间必须超过该开业典礼时间的一半并且不能打断。请问马耘如何安排他的日程,以便他能够出席所有的开业典礼? 请注意: 马耘不能在同一时间参加两个开业典礼; 马耘只能在整数时间加入或者退出开业典礼; 马耘可以在他完成前一个开业典礼后马上出现在另一个开业典礼上。 设计一个算法,判断马耘能否参加所有的开业典礼

输入

第一行包含一个整数n ( 0 <= n <= 10000 ),表示共有n 家商铺开张。接下来的n 行,每行包含两个整数Si 和Ti,分别表示开业典礼的开始时间和结束时间。( 0 <=Si,Ti <= 2^31 )。

输出
如果马耘可以参加所有的开业典礼,输出“YES” 。否则,输出“NO”。(结尾加一个换行符)

1
2
3
4
5
6
样例输入
2
1 5
4 6
样例输出
YES

思路:
首先对时间进行处理 比如 1-6这个时间段 真正被占用的 只用1-4
所以做法是 s=1 end=1+(6-1)/2+(6-1)%2 即可得到真正的时间,
每次新加入的时间段是之前所有时间段进行比较,如果 相交就no 所有数据没问题就yes
代码:

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
#include <iostream>
using namespace std;
bool isNO(int a,int b,int a1,int b1){
if (a>=b1|| b<=a1) {
return false;
}
else
{
return true;
}

}
int main() {
int n;
int a[10001][2];
int flag = 0;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i][0];
cin >> a[i][1];
a[i][1] = a[i][0] + (a[i][1] - a[i][0]) / 2 + (a[i][1] - a[i][0]) % 2;
for (int j = 0; j < i; j++) {
if (isNO(a[j][0], a[j][1], a[i][0], a[i][1])) {
flag = 1;
break;
}
}
if (flag == 1) break;
}
if (flag == 1) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
return 0;
}