繁忙的企业家

繁忙的企业家
问题描述：
马耘是一家上市公司的董事长。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<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<math.h>
 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<b.mid;//按中位数时间从小到大排序
14 }
15 int main() 
16 { 
17     int i,n,ansj,ansk,sum,t; 
18     
19     scanf("%d",&n); 
20     for(i=0;i<n;i++) {
21         scanf("%d %d",&data[i].k,&data[i].j);
22         data[i].mid=((double)(data[i].j+data[i].k))/2;
23     }
24     sort(data,data+n,cmp);//按照结束时间从小到大排序
25     
26     //for(i=0;i<n;i++)
27     //    printf("[%d %d] mid=%lf\n",data[i].k,data[i].j,data[i].mid);
28     
29     int lastj=floor(((double)data[0].j-(double)data[0].k)/2)+data[0].k+1;//参加的时间必须超过一半
30     ansk=data[0].k;//开始时间
31     ansj=lastj;//结束时间
32     //printf("1-[%d->%d]\n",ansk,ansj);
33     
34     for(i=1,sum=1;i<n;i++) 
35     { 
36         if(data[i].k>=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     else
61         printf("NO\n");    
62     return 0; 
63 }