2011-12-16 23:03:04

地址：

题意：一个过道，旁边有如图所示分布的办公室。有n张桌子，分别要从s[i]搬到t[i]，每张桌子要搬10min，同一段过道内同一个时间只能有一张桌子存在。问最少需要的分钟数。

mark：其实就是最大重叠数。wa了一次，注意同一个点出来的两张桌子，如果一个往左，一个往右，不可以同时进行。

代码：

# include 
     
       # include 
      
        typedef struct node{
   int a, b ; }node ; node pt[500] ; int min(int a, int b){
   return a
       
        b?a:b;} int cmp(const void *a, const void *b) {
       node *p = (node*)a, *q = (node*)b ; if (p->a != q->a) return p->a - q->a ; return q->b - p->b ; } int main () {
   int i, T ; int n, aa, bb, a, b ; int ans, cur ;     scanf ("%d", &T) ; while (T--)     {
           scanf ("%d", &n); for (i = 0; i < n ; i++)         {
               scanf ("%d%d", &aa, &bb) ;             a = (min(aa,bb)+1) / 2 ;             b = (max(aa,bb)+1) / 2 ;             pt[i*2].a = a, pt[i*2].b = 1 ;             pt[i*2+1].a = b, pt[i*2+1].b = -1 ;         }         qsort(pt, n*2, sizeof(node), cmp) ;         ans = cur = 0 ; for (i = 0 ; i < 2*n ; i++)         {
               cur += pt[i].b ;             ans = max(ans, cur) ;         }         printf ("%d\n", ans*10) ;     } return 0 ; }