作者在 2010-12-29 12:40:02 发布以下内容
1.Description
今天Ckp打算去约会。大家都知道Ckp是超级大帅哥，所以和他约会的MM也超级多，她们每个人都和Ckp订了一个约会时间。但是今天Ckp刚打算出门的时候才发现，某几个MM的约会时间有冲突。由于Ckp不会分身，还不能和多个MM同时约会，他只能忍痛割爱拒绝掉某些MM。但是Ckp这个花心大萝卜还是不死心，他想知道，他最多可以和多少个MM约会。Input
输入的第一行包含一个正整数N(0<N<=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的名字，用空格隔开。您可以按照任意的顺序输出。如果存在多个答案，您可以任选一个输出。
Sample Input
4
Lucy 06:00 10:00
Lily 10:00 17:00
HanMeimei 16:00 21:00
Kate 11:00 13:00
Sample Output
3
Lucy Kate HanMeimei
#include <iostream>
using namespace std;
struct MM{
char name[16];
char s[6];
char f[6];
};
MM mm[1000];
int x[1000];
void swap(int i, int j)
{
char tmp[16];
strcpy(tmp, mm[i].name);
strcpy(mm[i].name, mm[j].name);
strcpy(mm[j].name, tmp);
strcpy(tmp, mm[i].s);
strcpy(mm[i].s, mm[j].s);
strcpy(mm[j].s, tmp);
strcpy(tmp, mm[i].f);
strcpy(mm[i].f, mm[j].f);
strcpy(mm[j].f, tmp);
}
int partion(int p, int q)
{
int t=rand()%(q-p+1)+p;
swap(t,p);
int i=p;
int j=q+1;
while(true)
{
while(strcmp(mm[++i].f,mm[p].f)<0);
while(strcmp(mm[--j].f,mm[p].f)>0);
if(i>=j)break;
swap(i,j);
}
swap(p,j);
return j;
}
void quicksort(int p, int q)
{
if(p<q)
{
int r=partion(p,q);
quicksort(p,r-1);
quicksort(r+1,q);
}
}
void GreedySelect(int n)
{
int i,j,count;
quicksort(0,n-1);
j=0;
count=1;
x[0]=1;
for(i=1;i<n;i++)
{
if(strcmp(mm[i].s, mm[j].f)>=0)
{
x[i]=1;
count++;
j=i;
}
else
{
x[i]=0;
}
}
printf("%d\n",count);
for(i=0;i<n;i++)
{
if(x[i])
printf("%s ",mm[i].name);
}
printf("\n");
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%s%s%s", mm[i].name, mm[i].s, mm[i].f);
GreedySelect(n);
return 0;
}
using namespace std;
struct MM{
char name[16];
char s[6];
char f[6];
};
MM mm[1000];
int x[1000];
void swap(int i, int j)
{
char tmp[16];
strcpy(tmp, mm[i].name);
strcpy(mm[i].name, mm[j].name);
strcpy(mm[j].name, tmp);
strcpy(tmp, mm[i].s);
strcpy(mm[i].s, mm[j].s);
strcpy(mm[j].s, tmp);
strcpy(tmp, mm[i].f);
strcpy(mm[i].f, mm[j].f);
strcpy(mm[j].f, tmp);
}
int partion(int p, int q)
{
int t=rand()%(q-p+1)+p;
swap(t,p);
int i=p;
int j=q+1;
while(true)
{
while(strcmp(mm[++i].f,mm[p].f)<0);
while(strcmp(mm[--j].f,mm[p].f)>0);
if(i>=j)break;
swap(i,j);
}
swap(p,j);
return j;
}
void quicksort(int p, int q)
{
if(p<q)
{
int r=partion(p,q);
quicksort(p,r-1);
quicksort(r+1,q);
}
}
void GreedySelect(int n)
{
int i,j,count;
quicksort(0,n-1);
j=0;
count=1;
x[0]=1;
for(i=1;i<n;i++)
{
if(strcmp(mm[i].s, mm[j].f)>=0)
{
x[i]=1;
count++;
j=i;
}
else
{
x[i]=0;
}
}
printf("%d\n",count);
for(i=0;i<n;i++)
{
if(x[i])
printf("%s ",mm[i].name);
}
printf("\n");
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%s%s%s", mm[i].name, mm[i].s, mm[i].f);
GreedySelect(n);
return 0;
}
