HDU 2037 （貪心），hdu2037貪心
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2037
今年暑假不AC
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 31608 Accepted Submission(s): 16733
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
簡單的貪心題，詳解可查《算法競賽入門經典》152頁。
![]()
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 using namespace std;
5
6 int a[111],b[111];
7 int n,end,cnt;
8
9 int main ()
10 {
11 int i,j;
12 while (scanf ("%d",&n),n)
13 {
14 for (i=0; i<n; i++)
15 scanf ("%d %d",&a[i],&b[i]);
16 for (i=0; i<n; i++)
17 for (j=i; j<n; j++)
18 {
19 if (b[i] > b[j])
20 {
21 swap(b[i], b[j]);
22 swap(a[i], a[j]);//交換函數
23 }
24 }
25 cnt = 1;
26 end = b[0];
27 for (i=1; i<n; i++)
28 {
29 if (a[i] >= end)
30 {
31 cnt++;
32 end = b[i];
33 }
34 }
35 printf ("%d\n",cnt);
36 }
37 return 0;
38 }
View Code
