HDU 2037 - 今年暑假不AC(貪心)

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

Sample Output

5

Solution

1. 貪心算法，每次都選結束時間最早的節目去看。這樣就有更多的時間去看其他節目了。
2. 結束時間不大于下一個節目的開始時間，才算能看完完整的電視節目。
3. 定義二維數組a[N][2]
4. a[i][0]表示開始時間
5. a[i][1]表示結束時間
6. 從第一個節目必看，從i=1(也就是第二個節目開始判斷)，star=a[0]1，剩下的看代碼吧

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = ;
int a[N][];
int n;
int i, j;

/*

對二維數組 按列進行冒泡排序

*/
void bubble(int n)
{
    for (i = ; i < n; i++)
        for (j = ; j < n - i; j++)
        {
            if (a[j - ][] > a[j][])
            {
                swap(a[j - ][], a[j][]);//這裡圖個友善直接用swap()方法了
                swap(a[j - ][], a[j][]);
            }
            else if (a[j - ][] == a[j][])
                if (a[j - ][] > a[j][])
                {
                    swap(a[j - ][], a[j][]);
                    swap(a[j - ][], a[j][]);
                }
        }
}

int main()
{

    int ans, star;
    while (scanf_s("%d", &n) && n)
    {
        for (i = ; i < n; i++)
            scanf_s("%d%d", &a[i][], &a[i][]);
        bubble(n);//對二維數組進行冒泡排序
        for (i = , star = a[][], ans = ; i <n; i++)
        {
            if (a[i][] >= star)
            {
                star = a[i][];
                ans++;
            }
        }
        printf("%d\n", ans);

    }
    return ;
}