繁忙的企业家

问题描述：

马耘是一家上市公司的董事长。10 月 1 号是马耘最繁忙的一天，因为这一天有 n 家商

铺开张，而马耘必须在每家商铺的开业典礼上剪彩，马耘出席时间必须超过该开业典礼时间

的一半并且不能打断。请问马耘如何安排他的日程，以便他能够出席所有的开业典礼？

请注意：

马耘不能在同一时间参加两个开业典礼；

马耘只能在整数时间加入或者退出开业典礼；

马耘可以在他完成前一个开业典礼后马上出现在另一个开业典礼上。

编程任务：

设计一个算法，判断马耘能否参加所有的开业典礼。

数据输入：

第一行包含一个整数 n （ 0 <= n <= 10000 ），表示共有 n 家商铺开张。接下来

的 n 行，每行包含两个整数 Si 和 Ti，分别表示开业典礼的开始时间和结束时间。 （ 0 <=

Si,Ti <= 2^31 ）

结果输出:

如果马耘可以参加所有的开业典礼，输出 “YES” 。否则，输出 “NO”。

输入示例 输出示例

2 1

5

4 6

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std;  6 struct st  7 {  8     int k,j; 9     double mid;10 }data[10010]; 11 int cmp(st a,st b)12 {13     return a.mid
         
          %d]\n",ansk,ansj);33     34     for(i=1,sum=1;i
          
           =ansj)//开始时间大于上一场结束时间37 { 38 lastj=floor(((double)data[i].j-(double)data[i].k)/2)+data[i].k+1;//参加的时间必须超过一半39 ansk=data[i].k;//开始时间40 ansj=lastj;//结束时间41 // printf("2-[%d->%d]\n",ansk,ansj);42 sum++;43 }44 else//开始时间小于上一场时间45 { 46 int nowlen=floor(((double)data[i].j-(double)data[i].k)/2)+1;//参加的时间必须超过一半47 if(data[i].j-ansj>=nowlen)48 {49 sum++; 50 ansk=ansj;51 ansj=ansj+nowlen;52 //printf("3-[%d->%d]\n",ansk,ansj); 53 }54 55 }56 } 57 //printf("sum=%d\n",sum);58 if(sum==n)59 printf("YES\n");60 else61 printf("NO\n"); 62 return 0; 63 }