HDOJ 2037 今年暑假不AC

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2037

这题比 HDOJ 1009 FatMouse’ Trade 要稍微麻烦些。

思路:先把时间表按结束时间从小到大排列,然后可以推断出,结束时间te最小的节目一定在最长序列里。然后以结束时间尽量小的顺序接着找开始时间比上一个已确定的节目结束时间大且尽量晓得节目。

表达有点困难,大家分析下代码,应该不难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Author: Tanky Woo
// HDOJ 2037
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef struct TIME
{
    int ts;
    int te;
}TIME;
 
TIME time_table[101];
// www.wutianqi.com
int cmp(TIME a, TIME b)
{
    return (a.te < b.te);
}
 
int n;
int main()
{
    //freopen("input.txt", "r", stdin);
    while(scanf("%d", &n) && n)
    {
        for(int i = 0; i < n; ++i)
            scanf("%d %d", &time_table[i].ts, &time_table[i].te);
        sort(time_table, time_table+n, cmp);   //按te由小到大排列
        //for(int i = 0; i < n; ++i)
            //printf("%d %d\n", time_table[i].ts, time_table[i].te);
        // 目的:是te尽量小的同时,再使ts也尽量小
        int cnt = 0, sum = 1;  //最小的te的那个节目是一定要包括进去的
        for(int i = 1; i < n; ++i)
        {
            if(time_table[i].ts >= time_table[cnt].te)
            {
                cnt = i;
                sum++;
            }
        }
        printf("%d\n", sum);
 
    }
    return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 2037 今年暑假不AC》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注