Sail


手在键盘敲很轻


法师康的工人

Preface

本题的题目和答案依次戳


题目

三个法师康的工人每天早上6点到工厂开始到三条产品生产线上组装桔子手机。第一个工人在200时刻开始(从6点开始计时,以秒作为单位)在生产线上开始生产,一直到1000时刻。第二个工人,在700时刻开始,在1100时刻结束。第三个工人从1500时刻工作到2100时刻。期间最长至少有一个工人在生产线上工作的连续时间为900秒(从200时刻到1100时刻),而最长的无人生产的连续时间(从生产开始到生产结束)为400时刻(1100时刻到1500时刻)。

你的任务是用一个程序衡量N个工人在N条产品线上的工作时间列表(1≤N≤5000,以秒为单位)。

最长的至少有一个工人在工作的时间段

最长的无人工作的时间段(从有人工作开始计)

输入第1行为一个整数N,第2-N+1行每行包括两个均小于1000000的非负整数数据,表示其中一个工人的生产开始时间与结束时间。输出为一行,用空格分隔开两个我们所求的数。


样例输入

1
2
3
4
3
200 1000
700 1100
1500 2100

样例输出

900 400


题解

本题思路挺简单的。先将工人时间排序,开始时间越小越靠前,开始时间相同则结束时间越小的越靠前。
然后遍历的同时,更新求解的值即可。


Code

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
#include <iostream>
#include <algorithm>
#define max(a,b) (a>b)?a:b;
using namespace std;

int n;
struct node{
int left,right;
}a[5050];

bool cmp(node x,node y){
if(x.left == y.left) return x.right < y.right;
else return x.left < y.left;
}

int main() {
cin >> n;
for(int i = 0; i < n; i++){
cin>>a[i].left>>a[i].right;
}
sort(a,a+n,cmp);

int personTime = a[0].right - a[0].left;
int noPersonTime = 0;
int startTime = a[0].left,endTime = a[0].right;

for(int i = 1; i < n; i++){
if(a[i].left > endTime){
noPersonTime =max(noPersonTime,a[i].left - endTime);
startTime = a[i].left;
}
endTime = max(endTime,a[i].right);
personTime = max(personTime,endTime - startTime);
}
cout << personTime <<" "<<noPersonTime<<endl;
return 0;
}
© 2016-2019. | 由Hexo强力驱动 | 主题Huno | 渝ICP备17002561号 | 不装弱了,我要做大佬