Chinaunix首页 | 论坛 | 博客
  • 博客访问: 43325
  • 博文数量: 23
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 137
  • 用 户 组: 普通用户
  • 注册时间: 2014-07-21 11:10
个人简介

作为一名计算机专业的白丁,我还在摸索。

文章分类

全部博文(23)

文章存档

2014年(23)

我的朋友

分类: C/C++

2014-07-23 21:12:27

Description

“今年暑假不AC?” 
“是的。” 
“那你干什么呢?” 
“看世界杯呀,笨蛋!” 
“@#$%^&*%...” 

确实如此,世界杯来了,球迷的节日也来了,估计很多ACMer也会抛开电脑,奔向电视了。 
作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非常6+7、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的完整节目) 
 

Input

输入数据包含多个测试实例,每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数,然后是n行数据,每行包括两个数据Ti_s,Ti_e (1<=i<=n),分别表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结束,不做处理。 
 

Output

对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。
 

Sample Input

12 
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
 

Sample Output

5

#include
#include
using namespace std;
struct gro    //节目类
{
    int s;    //开始时间
    int e;    //结束时间
};
gro *g;


bool cmp(gro a,gro b)
{
    return a.e }
int main()
{
    int n,ans,i;
    while(cin>>n&&n!=0)
    {
        g=new gro[n];    //动态分配空间
        for(i=0;i         {
            cin>>g[i].s>>g[i].e;
        }
        sort(g,g+n,cmp);  //按e从小到大顺序对数组g排序(排序标准由cmp决定),g表示数组起始地址,g+n表示数组结尾地址的下一地址。
        ans=1;
        gro t;
        t=g[0];
        for(i=1;i         {
            if (t.e<=g[i].s)
            {
                ans++;
                t=g[i];
            }
        }
        cout<         delete g;
    }
    return 0;
}

简单的贪心问题
注意:
<1>以开始时间由小到大为标准,反例很明显:
假设有6组数据如下:

结果(上)为2,但正确结果(下)应为4.
<2>以经过时间由短到长为标准,反例:
假设有7组数据如下:

结果(上)为2,但正确结果(下)应为4.

阅读(318) | 评论(0) | 转发(0) |
0

上一篇:sort函数的用法

下一篇:欧几里得算法

给主人留下些什么吧!~~