Uva1420 Priest John's Busiest Day

John is the only priest in his town. October 26th is the John's busiest day in a year because there is an old legend in the town that the couple who get married on that day will be forever blessed by the God of Love. This year N couples plan to get married on the blessed day. The i -th couple plan to hold their wedding from time S_ito time T_i . According to the traditions in the town, there must be a special ceremony on which the couple stand before the priest and accept blessings. Moreover, this ceremony must be longer than half of the wedding time and can't be interrupted. Could you tell John how to arrange his schedule so that he can hold all special ceremonies of all weddings?

Please note that:

John can not hold two ceremonies at the same time.

John can only join or leave the weddings at integral time.

John can show up at another ceremony immediately after he finishes the previous one.

Input

The input consists of several test cases and ends with a line containing a zero. In each test case, the first line contains a integer N (1 $\le$ N $\le$ 100, 000) indicating the total number of the weddings. In the next N lines, each line contains two integers S_i and T_i ( 0 $\le$ S_i < T_i $\le$ 2147483647).

Output

For each test, if John can hold all special ceremonies, print ``YES"; otherwise, print ``NO".

Sample Input

Sample Output

NO 
YES
题目大意：牧师有N个婚礼需要参加，每个婚礼有一个起始时间s和结束时间t，牧师可以在婚礼进行时间的时段去，并主持仪式，持续时间至少超过婚礼总时间的一半。问牧师能否完成所有婚礼的仪式。
题解：贪心问题。计算出每个婚礼的中间时间，然后用中间时间进行升序排序，如果中间时间相等，则开始时间小的排前面。用变量ans表示上一个婚礼仪式完成的时间，如果ans小于当前婚礼的开始时间，则当前婚礼的仪式从婚礼的开始时间举行，否则的话就从ans开始举行。如果ans加上当前婚礼总时间的一半超过了婚礼结束时间，则说明当前婚礼的仪式不能够完成，因此牧师无法完成所有的婚礼仪式。（刚开始“婚礼的中间时间”和“婚礼的总时间的一半”两者没搞清楚。。WA了好多次。。。）

View Code

 1 #include<stdio.h>
 2 #include<math.h>
 3 #define MAXN 100005
 4 typedef struct
 5 {
 6     long s,t,mid,h;
 7 } NODE;
 8 NODE a[MAXN];
 9 long n;
10 void qsort(long l,long r)
11 {
12     long i,j;
13     NODE midd,temp;
14     i=l;
15     j=r;
16     midd=a[(l+r)>>1];
17     while(i<=j)
18     {
19         while((a[i].mid<midd.mid)||((a[i].mid==midd.mid)&&(a[i].s<midd.s))) i++;
20         while((a[j].mid>midd.mid)||((a[j].mid==midd.mid)&&(a[j].s>midd.s))) j--;
21         if(i<=j)
22         {
23             temp=a[i];
24             a[i]=a[j];
25             a[j]=temp;
26             i++;
27             j--;
28         }
29     }
30     if(i<r) qsort(i,r);
31     if(j>l) qsort(l,j);
32 
33 }
34 int main(void)
35 {
36     long i,ans;
37     while(scanf("%ld",&n)==1&&n)
38     {
39         for(i=0; i<n; i++)
40         {
41             scanf("%ld%ld",&a[i].s,&a[i].t);
42             a[i].h=((a[i].t-a[i].s)>>1)+1;
43             a[i].mid=a[i].s+a[i].h;
44         }
45         qsort(0,n-1);
46         ans=a[0].mid;
47         for(i=1; i<n; i++)
48             {
49                  if(ans+a[i].h>a[i].t)
50                  break;
51                  if(ans<a[i].s)
52                  ans=a[i].mid;
53                  else
54                  ans+=a[i].h;
55             }
56         if(i==n) printf("YES\n");
57         else
58         printf("NO\n");
59     }
60     return 0;
61 }