---

想说的话

炎热的夏天马上就要来临啦,小编今天以杭电ACM"今年暑假不AC"（hdu2037）作为索引跟大家简单介绍一下经典的贪心算法,以及两种简单排序的方法
作为一个优秀的ACMer肯定不能错过一个暑假提升的机会。

话不多说,进入正文

---

一、今年暑假不AC

老样子,我们先来看看题目,理解题目才是解题的关键

--------------------第16题（hdu2037）------------------
（1）题目
今年暑假不AC
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem 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

看完了题目你是否有了大致的思路了呢
题目主要考察的是我们对贪心算法是否熟练

解题思路

题目意思是想让我们在一天内尽可能看最多数量的节目,
那么我们

1、节目开始时间较早的
2、第二个节目的开始时间不能早于第一个节目的结束时间

对于第一个需要解决的就是对所有的节目开始时间从小到大进行排序
知识点：用“结构体+qsort()”做贪心
qsrot(首地址，结束地址，类型大小，比较器)

一、对int类型数组排序 
int num[100]; 
int cmp ( const void *a , const void *b ) { 
return *(int *)a - *(int *)b;    //升序 降序b-a
} 
qsort(num,100,sizeof(num[0]),cmp); 

或者
知识点：c++标准库中头文件为#include + sort（）函数
sort(开始地址，结束地址)

#include<iostream>
#include<algorithm>
using namespace std;
main()
{
　　//sort函数第三个参数采用默认从小到大
　　int a[]={45,12,34,77,90,11,2,4,5,55};
　　sort(a,a+10);    //默认升序
　　for(int i=0;i<10;i++)
　　cout<<a[i]<<" ";
}

二、学会简单排序

1.比较器+qsort（）函数

我们将从int、double、char三种简单类型进行排序
第一步：要写好比较器
第二部：需要排序的地方调用qsret（）函数

代码如下（示例）：

#include"bits/stdc++.h"
using namespace std;

int cmp1(const void *a,const void *b)
{
	return *(double *)a>*(double *)b?1:-1;
}                 //比较器

int cmp2(const void *a,const void *b)
{
	return *(int*)a-*(int *)b;
}                 //比较器       

int cmp3 (const void *a,const void *b)
{
	return *(char*)a-*(char *)b;
}                 //比较器

int main()
{
	double a[]={1.2,2.3,31.33,2.44,4.22,1.444,41.22};
	int b[]={12,31,24,45,54,35,46,54,6,544,54,46,567,5};
	char c[]={'s','a','w','a','b','c','A','B','C','d'};
	
	int x1=sizeof(a)/sizeof(a[0]);
	int x2=sizeof(b)/sizeof(b[0]);
	int x3=sizeof(c)/sizeof(c[0]);   //测量大小
	
	qsort(a,x1,sizeof(a[0]),cmp1);   //排序
	qsort(b,x2,sizeof(b[0]),cmp2);
	qsort(c,x3,sizeof(c[0]),cmp3);
	
	while(x1--){	    //循环输出
	int i;	
		cout<<a[i]<<" ";
		i++;
	}
	cout<<endl;
		while(x2--){	
		int i;	
			cout<<b[i]<<" ";
			i++;
		}
	cout<<endl;
		while(x3--){	
		int i;	
		cout<<c[i]<<" ";
		i++;
	}
	return 0;
}

想了解sort函数小伙伴的可以查看：Ahual 八种qsort()用法

2头文件+sort（）函数

我们将从int、double、char三种简单类型进行排序
第一步：要写好头文件#include
第二部：需要排序的地方调用sret（）函数

代码如下（示例）：

#include<algorithm>   //包含sort（）函数
#include<iostream>
using namespace std;

int main()
{
	double a[]={1.2,2.3,31.33,2.44,4.22,1.444,41.22};   //样例数据
	int b[]={12,31,24,45,54,35,46,54,6,544,54,46,567,5};
	char c[]={'s','a','w','a','b','c','A','B','C','d'};
	
	int x1=sizeof(a)/sizeof(a[0]);   //测量大小
	int x2=sizeof(b)/sizeof(b[0]);
	int x3=sizeof(c)/sizeof(c[0]);
	
	sort(a,a+x1);          //升序排序
	sort(b,b+x2);
	sort(c,c+x3);
	
	while(x1--){	 //循环输出
	int i;	
		cout<<a[i]<<" ";
		i++;
	}
	cout<<endl;
		while(x2--){	
		int i;	
			cout<<b[i]<<" ";
			i++;
		}
	cout<<endl;
		while(x3--){	
		int i;	
		cout<<c[i]<<" ";
		i++;
	}
	return 0;
}

若需要进行降序排序只需在函数末尾添加 “greater<数据类型>()”

sort(a,a+x1,greater<double>());
sort(b,b+x2,greater<int>());
sort(c,c+x3,greater<char>());

想了解sort函数小伙伴的可以查看：俊宝贝 C++中SORT函数使用方法

---

我们发现直接使用万能头文件"#include<bits/stdc++.h>"+sort()函数 ，很大程度上简化了代码量，对一个精益求精的acmer简直不要太好用了

三、AC才是王道

说了这么多废话，当然要能解题才是关键

1.常规解法

/*  思路：先给节目按结束时间排序
然后用贪心依次选取“尚未开始但结束时间最早”的节目  */
#include<stdio.h>
int main()
{
    int i,j,k; //游标
    int n; //节目数
    int a[105][2], tmp[2]; //存储节目

    while( scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;

        //输入n个节目(起始时间a[i][0] 和 结束时间a[i][1] )
        for(i=0;i<n;i++)
            scanf("%d%d",&a[i][0],&a[i][1]);

         //对所有节目按结束时间排序----优先队列
         for(i=0;i<n-1;i++)
            for(j=i+1;j<n;j++)
             {
                if(a[i][1]>a[j][1])
                {
                    tmp[0]=a[i][0],tmp[1]=a[i][1];
                    a[i][0]=a[j][0],a[i][1]=a[j][1];
                    a[j][0]=tmp[0],a[j][1]=tmp[1];
                }//进行贪心选择:依次从优先队列(排完序的数组)
             }//中选择“尚未开始”的节目(最有利)
         j=1;//题解(节目数统计)
         k=a[0][1];//记录上一节目的结束时间
         for(i=1;i<n;i++)
         {
             if( a[i][0]>= k )
             {
                 k=a[i][1];//更新上一节目的结束时间
                 j++;
             }
         }
         printf("%d\n",j);
    }
    return 0;
}

2.模板“结构体+qsort()”

#include<stdio.h>
#include<stdlib.h>
#define MAXN 105

struct node{
  int start;
  int end;
}record[MAXN];

int cmp(const void *a, const void *b)
{
    struct node *x = (struct node *)a;
    struct node *y = (struct node *)b;
    return x->end - y->end;
}					//比较器

int main()
{
    int n,count,lastEnd;
    while( scanf("%d",&n)!=EOF)
    {
        if(n==0) break;

        //输入n个节目的数据
        for(int i=0;i<n;i++)
            scanf("%d%d",&record[i].start,&record[i].end);

        //排序：按结束时间升序  -->优先队列
        qsort(record,n,sizeof(record[0]),cmp);  //时间复杂度:nlogn
        
        //进行贪心选择
        count=0;
        lastEnd=-1;
        for(int i=0;i<n; i++)
        {
            if(record[i].start >= lastEnd)
            {
                count++;
                lastEnd = record[i].end;
            }
        }
        //输出结果
        printf("%d\n",count);
    }
    return 0;
}

总结

今天的分享就到这里啦，本文仅仅简单介绍了用贪心算法解决杭（hdu2037)，首先讲解了大致的解题思路，介绍了两种基本的排序方法（主要哦结构体比较特殊不能用以上方法），扩展链接有详细介绍，最后以两种解题方法拿下AC!!!

喜欢小编博客的可以点赞支持哦，觉得内容对你有用的可以收藏备用
最后，祝我们早日抗疫成功，摘下口罩和最想见面的人见面，齐心抗疫