首页 > ACM题库 > HDU-杭电 > HDU 2779-HOJ-Party Party Party-贪心-[解题报告]C++
2014
02-14

HDU 2779-HOJ-Party Party Party-贪心-[解题报告]C++

Party Party Party

问题描述 :

Emma has just graduated high school and it is the custom for the new graduates to throw parties for themselves and invite everyone in school to attend. Naturally, Emma wishes to attend as many parties as possible. This is not such a problem on a weekday since usually there are only two or three parties in the evening. But, Saturdays are packed! Typically some parties start at 8 AM (breakfast is served) while others might end at midnight (much to the annoyance of the neighbors). Emma naturally wants to know how many parties she can attend.

Each party has a starting and stopping time, which are on the hour. These are listed via a 24-hour clock. For example, a party might start at 10 AM (10) and end at 2 PM (14). The earliest a party can start is 8 AM (8) and the latest it can end is midnight (24). In order not to be rude, Emma stays at each party at least one half hour and will consider traveling time between parties to be instantaneous. If there are times during the day when there are no parties to attend, she’ll simply go home and rest.

输入:

There will be multiple test cases. Each test case starts with a line containing an integer p (<=100) indicating the number of parties on the given day. (A value of p = 0 indicates end of input.) The following p lines are each of the form s e , both integers where 8<=s < e<=24 , indicating a party that starts at time s and ends at time e . Note there may be multiple parties with the same starting and ending time.

输出:

There will be multiple test cases. Each test case starts with a line containing an integer p (<=100) indicating the number of parties on the given day. (A value of p = 0 indicates end of input.) The following p lines are each of the form s e , both integers where 8<=s < e<=24 , indicating a party that starts at time s and ends at time e . Note there may be multiple parties with the same starting and ending time.

样例输入:

8 
12 13 
13 14 
12 13 
9 10 
9 10 
12 13 
12 14 
9 11 
3 
14 15 
14 15 
14 15 
0

样例输出:

On day 1 Emma can attend as many as 7 parties. 
On day 2 Emma can attend as many as 2 parties.


贪心!每次半小时贪心一下,在能参加的party中取结束时间最早的,这样就能保证最优!


#include<stdio.h>
#include<string.h>


struct ss {
    int x, y;
} s[105];


int main() {
    int n, i, min, d, k, ans, t;
    int mark[101], v = 1;
    while (scanf(“%d”, &n), n) {
        for (i = 1; i <= n; i++) {
            scanf(“%d %d”, &s[i].x, &s[i].y);
            s[i].x *= 10;
            s[i].y *= 10;
            mark[i] = 0;
        }
        ans = 0;
        t = 80;
        while (t <= 240) {
            k = 0;
            min = 1000;
            for (i = 1; i <= n; i++)
                if (!mark[i]) {
                    if (s[i].x == t || (t + 5 <= s[i].y && t > s[i].x)) {
                        if (min > s[i].y) {
                            k = i;
                            min = s[i].y;
                        }
                    }
                }
            if (k) {
                ans++;
                mark[k] = 1;
            }
            t += 5;
        }
        printf(“On day %d Emma can attend as many as %d parties.\n”, v++, ans);
    }
    return 0;
}

解题参考:http://zc634579757.blog.163.com/blog/static/124497462201012515232525/