xmu1061Ckp的约会

时间：2010-08-03 来源：hbj_2008

Description
　　今天Ckp打算去约会。大家都知道Ckp是超级大帅哥，所以和他约会的MM也超级多，她们每个人都和Ckp订了一个约会时间。但是今天Ckp刚打算出门的时候才发现，某几个MM的约会时间有冲突。由于Ckp不会分身，还不能和多个MM同时约会，他只能忍痛割爱拒绝掉某些MM。但是Ckp这个花心大萝卜还是不死心，他想知道，他最多可以和多少个MM约会。
Input
　　输入的第一行包含一个正整数N(0<=1000)，表示和Ckp约会的MM数。
　　接下去N行，每行描述一个MM，格式为: Name starttime endtime，表示在[starttime,endtime)这个半开区间是这个MM的约会时间，starttime < endtime。名字由大写或小写字母组成，最长不超过15个字母，保证没有两个人拥有相同的名字，所有时间采用24小时制，格式为XX:XX，且在 06:00到23:00之间。
Output
　　输出的第一行是一个整数M表示Ckp最多可以和多少个MM约会。
　　接下来那一行就是M个MM的名字，用空格隔开。您可以按照任意的顺序输出。如果存在多个答案，您可以任选一个输出。
分析：
这个题主要是用贪心算法，其中的子算法便是快排，分清结构后容易写出代码。

01    #include<iostream>
02    #include<cstdlib>
03    #define max 1001
04    char name[max][16];
05    char start[max][6];
06    char end[max][6];
07    using namespace std ;
08    void Quicksort(int *p,int* q,int* shunxun ,int n,int m)
09    {
10     int Partion(int *,int *,int*,int,int);
11     if(n<m)
12     {
13     int k = Partion(p,q,shunxun,n,m);
14     Quicksort(p,q,shunxun,n,k-1);
15     Quicksort(p,q,shunxun,k+1,m);
16     }
17    }
18    int Partion(int* p,int* q,int* shunxun,int n,int m)
19    {
20     void Swap(int* ,int,int);
21     int flag = p[m];
22     int i = n-1 ;
23     for(int j=n;j<m;j++)
24     if(p[j]<flag)
25     {
26     i++;
27     Swap(p,j,i);
28     Swap(q,j,i);
29     Swap(shunxun,j,i);
30     }
31     Swap(p,i+1,m);
32     Swap(q,i+1,m);
33     Swap(shunxun,i+1,m);
34     return i+1;
35    }
36    void Swap(int* p,int i,int j)
37    {
38     int temp;
39     temp = p[i];
40     p[i]=p[j];
41     p[j]=temp;
42    }
43    int main()
44    {
45     int n ;
46     int number = 0 ;
47     cin>>n;
48     for(int i=0;i<n;i++)
49     {
50     cin>>name[i];
51     cin>>start[i];
52     cin>>end[i];
53     }
54     int* starttime= new int[n];
55     int* endtime= new int[n];
56     int* que = new int[n];
57     int* shunxun = new int[n];
58     for(int i=0;i<n;i++)
59     {
60     starttime[i]=(start[i][0]-’0′)*1000+100*(start[i][1]-’0′)+10*(start[i][3]-’0′)+(start[i][4]-’0′);
61     endtime[i]=1000*(end[i][0]-’0′)+100*(end[i][1]-’0′)+10*(end[i][3]-’0′)+(end[i][4]-’0′);
62     shunxun[i]=i;
63     }
64     Quicksort(endtime,starttime,shunxun,0,n-1);
65     int Cendtime=endtime[0];
66     que[0]=shunxun[0];
67     for(int j=1;j<n;j++)
68     if(starttime[j]>=Cendtime)
69     {
70     number++;
71     que[number]=shunxun[j];
72     Cendtime= endtime[j];
73     }
74     cout<<number+1<<endl;
75     for(int j=0;j<number+1;j++)
76     cout<<name[que[j]]<<" ";
77     cout<<endl;
78     delete[] starttime,endtime,que,shunxun;
79     system("pause");
80     return 0 ;
81    }