usaco1.2.1 解题报告

题目来自acmore长沙理工oj

题目链接：http://www.acmore.net/problem.php?cid=1000&pid=0

题目描述：给定n个工人的工作时间，计算出最长的连续工作时间和空闲时间；

解题思路：对n个工人的工作时间的起点进行排序，然后依次遍历如果第i 个工人的工作起始时间< 第 i-1 个工人的工作结束时间，更新thou（临时工作结束时间）并计算tmax（临时工作时间长度），否则同时重置tqian（临时工作开始时间） thou tmax 并更新rmax（最长休息时间）

题目代码：

View Code

 1 /*Athor        : darkdream
 2 * Email         : darkdream1994@gmail.com 
 3 *  * Last modified : 2013-01-22 13:14
 4 *   * Filename      : test.c
 5 *    * Description   :
 6 *     * *********************************************************/
 7 #include <stdio.h>
 8 #include <stdlib.h>
 9 #define max(a,b) a>b?a:b
10 #define min (a,b) a<b ?b:a
11 struct time {
12     long int a, b;
13 };
14 
15 int cmp (const void *a,const void *b)
16 {
17     return (*(struct time *) a).a > (*(struct time *)b).a ? 1:-1;
18 }
19 
20 struct time a[6000];
21 int main(){
22     int n;
23 
24     long int  c , d, i , j;
25     scanf("%d",&n);
26     for (i = 0 ; i < n ; i++)
27     {    scanf("%ld %ld",&a[i].a,&a[i].b);
28         if (a[i].a > a[i].b)
29         {
30             c = a[i].a;
31             a[i].a = a[i].b;
32             a[i].b = c; 
33         }
34     }
35     qsort(a,n,sizeof(a[0]),cmp);
36 
37     long long int wmax = 0 ,rmax = 0,wsum = 0 ,tmax ,tqian,thou;
38     wmax = a[0].b - a[0].a;
39     tqian = a[0].a ;
40     thou = a[0].b;
41 
42 
43     wsum = wmax ;
44     for (i =1 ; i < n ; i++)
45     {
46         if (a[i].a <= thou) 
47         {
48 
49             thou = max(thou,a[i].b);
50 
51             wsum =thou-tqian;
52             if (wsum > wmax)
53                 wmax = wsum ;
54 
55         }
56         else
57         {
58             wsum = 0 ;
59             if (a[i].a - thou > rmax)
60                 rmax = a[i].a- thou;
61             tqian = a[i].a;
62             thou = a[i].b;
63             wsum =  thou - tqian;
64             if(wsum > wmax)
65                 wmax = wsum ;
66         }
67     }
68     printf("%lld %lld\n",wmax,rmax);
69 
70     return 0;
71 }