hdu 2600

地址：http://acm.hdu.edu.cn/showproblem.php?pid=2600

题意：给一个区间p和q表示年份。给n个战争的起始年份、终止年份和战争名字（其实无用）。问[p,q]区间内最大没有战争的年份是多少。

mark：600w*2的区间*100个战争如果直接开bool数组实在是很勉强。可以把战争先按起始年份再按终止年份排序，for一遍，维护一个last变量表示已经检查过的战争里最大的结束年份。具体看代码。

代码：

 1 # include <stdio.h>
 2 # include <stdlib.h>
 3 
 4 
 5 int a[110][2] ;
 6 int max(int a, int b){return a>b?a:b;}
 7 int cmp(const void *a, const void *b)
 8 {
 9     int *p = (int*)a, *q = (int*) b;
10     if (p[0] != q[0]) return p[0]-q[0] ;
11     return p[1]-q[1] ;
12 }
13 
14 
15 int main ()
16 {
17     int n, i, ans, last, p, q, INF = 0x0f0f0f0f;
18     while (~scanf ("%d%*c", &n))
19     {
20         scanf ("%d %d%*c", &p, &q) ;
21         for (i = 0 ; i < n ; i++)
22             scanf ("%d %d %*[^
]%*c", &a[i][0], &a[i][1]) ;
23         qsort(a, n, sizeof(a[0]), cmp) ;
24         ans = -INF ;
25         if (a[0][0] > p) ans = a[0][0]-1 ;
26         last = a[0][1] ;
27         for (i = 1 ; i < n ; i++)
28         {
29             if (a[i][0] > last+1) ans = a[i][0]-1 ;
30             last = max(last, a[i][1]) ;
31         }
32         if (last != q) ans = q ;
33         if (ans == -INF) printf ("Badly!
") ;
34         else printf ("%d
", ans) ;
35     }
36     return 0 ;
37 }