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
49
50
51
52
53
54
55
56
57
58
|
/*
ID: mytbk921
LANG: C
TASK: milk2
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXN 5000
#define max(a,b) ((a)>(b))?(a):(b)
typedef struct
{
int begin,end;
}TimeTab,*pTimeTab;
int comp(pTimeTab a,pTimeTab b)
{
return a->begin-b->begin;
}
int main()
{
int N;
int max_milk,max_nomilk;
int tBegin,tEnd;
int i;
TimeTab milktime[MAXN];
FILE *fin=fopen("milk2.in","r");
FILE *fout=fopen("milk2.out","w");
fscanf(fin,"%d",&N);
for (i=0;i<N;++i)
fscanf(fin,"%d%d",&milktime[i].begin,&milktime[i].end);
fclose(fin); //input complete
qsort(milktime,N,sizeof(TimeTab),(int(*)(const void*,const void*))comp);
max_milk=milktime[0].end-milktime[0].begin;
max_nomilk=0;
tBegin=milktime[0].begin;tEnd=milktime[0].end;
for (i=0;i<N;i++){
if (tEnd>=milktime[i].begin)
tEnd=max(tEnd,milktime[i].end);
else{
max_milk=max(tEnd-tBegin,max_milk);
max_nomilk=max(milktime[i].begin-tEnd,max_nomilk);
tBegin=milktime[i].begin;
tEnd=milktime[i].end;
}
if (i==N-1)
max_milk=max(tEnd-tBegin,max_milk);
}
fprintf(fout,"%d %d\n",max_milk,max_nomilk);
fclose(fout); //output complete
return 0;
}
|