首页 > ACM题库 > HDU-杭电 > hdu 2390 Olympic Games-贪心[解题报告]C++
2014
01-05

hdu 2390 Olympic Games-贪心[解题报告]C++

Olympic Games

问题描述 :

Mike loves the olympic games. What he hates about olympic games � besides them taking place only once every four years � is that the individual events are scheduled concurrently. That way it is never possible to watch all competitions live. Mike always tries to plan his personal schedule in order to maximize the number of events he can attend to. However, at the end he is never sure whether or not his schedule actually is optimal. Help him!

Given the days and times on which events take place, determine the maximum number of events Mike can watch. Mike never leaves during an event, so it is not possible to partially attend to events.

输入:

The input starts with a line containing a single integer n, the number of test cases.
Each test case starts with a line containing an integer 1 <= m <= 50000 that specifies the number of different events. The next m lines describe one event with three integers d, s, e. The event takes place on day d of the olympics, it starts at s and it ends at e, where the times are given in the form hhmm. All events are assumed to conclude the same day they started.

输出:

The input starts with a line containing a single integer n, the number of test cases.
Each test case starts with a line containing an integer 1 <= m <= 50000 that specifies the number of different events. The next m lines describe one event with three integers d, s, e. The event takes place on day d of the olympics, it starts at s and it ends at e, where the times are given in the form hhmm. All events are assumed to conclude the same day they started.

样例输入:

2
10
1 1220 1340
2 1155 1220
2 1220 1340
3 1220 1240
1 1200 1320
2 1250 1310
2 1330 1550
3 1030 1130
3 1130 1300
3 1240 1330
3
1 0500 2200
1 0000 0700
1 2000 2359

样例输出:

Scenario #1:
7

Scenario #2:
2


先给天数排序,同一天按结束时间排序,使用贪心就可以了

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct as
{
    int day;
    int sta;
    int end;
} p[50010];
int cmp(as a ,as b)
{
    if(a.day>b.day)
        return 0;
    else if(a.day==b.day)
        return a.end<b.end;
    else
        return 1;
}
int main()
{
    int t,n,i,time,sum,pos,ko=1;
    cin>>t;
    while(t--)
    {
        sum=0;
        cin>>n;
        for(i=0; i<n; i++)
            scanf("%d%d%d",&p[i].day,&p[i].sta,&p[i].end);
        sort(p,p+n,cmp);
        sum++;
        time=p[0].day;//记录天数
        pos=0;//用来记录当前的位置
        for(i=1; i<n; i++)
        {
            if(p[i].day==time&&p[i].sta>=p[pos].end)
            {
                sum++;
                pos=i;
            }
            if(p[i].day!=time)
            {
                time=p[i].day;
                pos=i;
                sum++;
            }
        }
        cout<<"Scenario #"<<ko<<":"<<endl;
        cout<<sum<<endl<<endl;
        ko++;
    }
}

 


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。