Ckp的约会(xmu oj)贪心算法问题 by C++

Ckp的约会(xmu oj)贪心算法问题 by C++

题目描述

Ckp的约会
描述
今天Ckp打算去约会。大家都知道Ckp是超级大帅哥,所以和他约会的MM也超级多,她们每个人都和Ckp订了一个约会时间。但是今天Ckp刚打算出门的时候才发现,某几个MM的约会时间有冲突。由于Ckp不会分身,还不能和多个MM同时约会,他只能忍痛割爱拒绝掉某些MM。但是Ckp这个花心大萝卜还是不死心,他想知道,他最多可以和多少个MM约会。

输入
输入的第一行包含一个正整数N(0<N<=1000),表示和Ckp约会的MM数。接下去N行,每行描述一个MM,格式为: Name starttime endtime,表示在[starttime,endtime)这个半开区间是这个MM的约会时间,starttime < endtime。名字由大写或小写字母组成,最长不超过15个字母,保证没有两个人拥有相同的名字,所有时间采用24小时制,格式为XX:XX,且在06:00到23:00之间。

输出
输出的第一行是一个整数M表示Ckp最多可以和多少个MM约会。接下来那一行就是M个MM的名字,用空格隔开。您可以按照任意的顺序输出。如果存在多个答案,您可以任选一个输出。

输入样例 1
4
Lucy 06:00 10:00
Lily 10:00 17:00
HanMeimei 16:00 21:00
Kate 11:00 13:00

输出样例 1
3
Lucy Kate HanMeimei

(我猜这题肯定是某位Ckp的同学或者同事写的)

题目分析

  • 算法分析
    本道题目的算法并不困难,得到输入的所有信息之后,我们可以发现只要按照结束时间,也就是题目里的endtime由早到晚的顺序让Ckp和相应的妹子约会,最后Ckp就能约到最多的妹子。这道题就是一道贪心算法题。

  • 输入问题
    那么问题就来了,这个输入看着就麻烦,我们这道题主要需要解决的就是输入问题。如何设置输入才能让得到的信息方便操作且清晰呢。最直接能想到的办法就是用结构体数组来记录每一个MM的信息。

typedef struct person{
    string Name;  //姓名
    string starttime;	// 开始时间
    string endtime;    // 结束时间
}person,*pPerson;

person girls[1010];  // 暂定上界为1010人(Ckp真是个花心大萝卜)

设置好之后,就可以输入了,C++中的cin输入函数也可以接受string类型,而且是碰到空格停止,非常适合我们这道题,所以直接用cin输入就好。

  • 排序问题
    输入解决!那么我们还需要设置一个函数使得输入的MM们按照他们有空的结束时间进行排序,排序我们再熟悉不过

###冒泡排序###

void sortByEndime(int n){
    for(int i =0 ; i < n-1; i ++ ){
        for(int j = 0 ; j < n-1-i ; j ++ ){
                if(girls[j].endtime > girls[j+1].endtime){
                    swap(girls[j],girls[j+1]);
                }
        }
    }
}

这里用了一下C++自带的swap函数。 但是,用冒泡排序的我被同学鄙视了,于是,

###使用C++内部的排序函数###

bool compare(  person a,person b  ){
    return a.endtime < b.endtime;
}
void sortByEndime(int n){
    sort(girls,girls+n,compare);
}

简单明了,速度还快。

那么我们就可以按照刚刚的算法分析写出完整代码了!

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
using namespace std;

typedef struct person{
    string Name;
    string starttime;
    string endtime;
//    int last_time;
    int is_on;
}person,*pPerson;
bool compare(  person a,person b  ){
    return a.endtime < b.endtime;
}
person girls[1010];
//int lastTime(person a){
//    int last = 0;
//    for(int i = 0 ; i <= 4 ; i ++ ){//因为有一个冒号所以要多循环一次
//        last = last*10 + (a.endtime[i]-a.starttime[i]);
//    }
//    return last;
//}

//void sortByLastime(int n){
//    for(int i =0 ; i < n-1; i ++ ){
//        for(int j = 0 ; j < n-1-i ; j ++ ){
//                if(girls[j].last_time > girls[j+1].last_time){
//                    swap(girls[j],girls[j+1]);
//                }
//        }
//    }
//
//}
void sortByEndime(int n){
//    for(int i =0 ; i < n-1; i ++ ){
//        for(int j = 0 ; j < n-1-i ; j ++ ){
//                if(girls[j].endtime > girls[j+1].endtime){
//                    swap(girls[j],girls[j+1]);
//                }
//        }
//    }
    sort(girls,girls+n,compare);
}

int main()
{
    int n;//总人数
//    int flag=0;//标记目前最早MM
//    int flag_late =0;//标记最晚MM
    int num=0;//约到的人数
    //输入
    cin>>n;
    int dates[n];
    memset(dates,-1,sizeof dates);
    for(int i = 0 ; i < n ; i ++){
        cin>>girls[i].Name;
        cin>>girls[i].starttime;
        cin>>girls[i].endtime;
        girls[i].is_on=0;
//        girls[i].last_time=lastTime(girls[i]);
    }
//    for(int i = 0 ; i < n ; i ++){
//        cout<<"姓名:"<<girls[i].Name;
//        cout<<"开始"<<girls[i].starttime;
//        cout<<"结束"<<girls[i].endtime;
//        cout<<"是否被约"<<girls[i].is_on<<"\n";
//        cout<<"持续时间"<<girls[i].last_time<<"\n";
//    }
    //按照结束时间排序,贪心算法
    sortByEndime(n);
//     for( int i = 0 ; i < n ; i ++ ){
//        cout<<girls[i].Name;
//    }

//    string earlytime = girls[0].starttime;
    string currentime = girls[0].endtime;
//    string latetime = girls[n-1].endtime;
    girls[0].is_on = 1;
//    for(int i = 0 ; i < n ; i ++ ){
//        if(girls[i].starttime < earlytime){
//            earlytime=girls[i].starttime;
//            flag = i;
//        }
//        if(girls[i].endtime > latetime){
//            latetime = girls[i].endtime;
//            flag_late = i;
//        }
//    }


    //核心代码
    dates[num] = 0;

        for(int i = 0 ; i < n ; i ++ ){
            if(girls[i].is_on == 0 && girls[i].starttime >= currentime){
                girls[i].is_on = 1;
                currentime = girls[i].endtime;
                num++;
                dates[num] = i;
//                cout<<"\n"<<num<<" "<<currentime<<"\n";

            }
        }

    //输出结果
    cout<<num+1<<"\n";
    for( int i = 0 ; i < num+1 ; i ++ ){
        cout<<girls[dates[i]].Name<<" ";
    }

    return 0;
}

因为途中尝试过用每位MM的有空持续时间解决问题,所以里面有已经被注释掉的一些函数和元素,说不定之后继续深化这个问题时能派上用场。还有一些注释是debug用(比如紧跟输入部分下面的,可以输出自己输入的信息)
还有结构体中的

int is_on;

是用来记录该女孩是否被约的,在本题中好像没啥用,但是在编程的一开始为了健壮性还是留下来了,整体看上去可能有些冗杂,以下为

代码截图:

Ckp的约会(xmu oj)贪心算法问题 by C++

上一篇:100 Most Influential Books According to Stack Overflow


下一篇:[2018HN省队集训D6T2] girls