HDU_2037.今年暑假不AC

Date： 2009 / 05 / 06

Problem Description：

 

Problem analysis：

第一次接触这题的时候没什么感觉，随着时间的推移，知道这题原来是要贪心的。当然也看过动态规划的算法，不过动态规划的那种不是很明白。贪心和动态规划是两个难点。一定要好好掌握。做个贪心王，哈哈。

大体思路是这样的：题目给定了节目的开始和结束时间，可以按结束时间对其排序。在结束时间一样的情况下，把开始时间早的排在前面。这样便形成了一个可以贪心的结构，从头开始遍历，把能够看的都看了。能够看的就是从第二个元素开始满足他的起始时间大于前一个元素的结束时间节目。具体实现代码如下，当然用库函数写会更精简点，但一些函数在练习的时候还是手工去实现比较好：

 

Code：

1#include <iostream>
 2
 3using namespace std;
 4
 5int main()
 6{
 7    //freopen("d:/test.in","r",stdin);
 8    int n,ts[101],te[101],i,j,k,t;
 9    while(cin>>n&&n)
10    {
11    for(i=0; i<n; ++i)
12    {
13        cin>>ts[i];
14        cin>>te[i];
15    }

        // sort
16    for(i=1; i<n; ++i)
17        for(j=0; j<n-i; ++j)
18            if(te[j]>te[j+1])
19            {
20                t=te[j];te[j]=te[j+1];te[j+1]=t;
21                t=ts[j];ts[j]=ts[j+1];ts[j+1]=t;
22            }

       //  select as much as you could
23    t=1;k=te[0];
24    for(i=0; i<n-1; ++i)
25       for(j=i+1; j<n; ++j)
26       {
27           if(k<=ts[j])
28           {
29               i=j-1;
30               k=te[j];
31               t++;
32               break;
33           }
34       }
35       cout<<t<<endl;
36    }
37}

 

@author: fleap