/*求解過程如下：首先對每個區間，以其起始坐標為關鍵字，從小到大排序。再依次找每查詢一次能覆蓋
到的最大的區間，假設還沒有看過的書頁為(sta , end)，每次可以查詢的小段區間用(xi , yi) 表示，
那么對于沒有找過的每段區間，我們都是找 xi<=sta，并且yi > sta的區間中yi最大的區間，直到yi = end為止。
最后統計區間的個數，即為最少的查詢次數。*/
1
#include <iostream>
2#include <algorithm>
3using namespace std;
4#include <string.h>
5
6struct book
7
{
8
int ai;
9 int bi;
10
}page[5001];
11
12bool cmp (const book &a, const book &b)
13{
14 return a.ai < b.ai;
15}
16int main ()
17{
18 int t, n;
19 while ( scanf ("%d", &t) != EOF )
20
{
21 for ( int i = 0; i < t; i ++ ) //t 組測試數據
22 {
23
24 memset (page, 0, sizeof (page));
25 scanf ("%d", &n);
26 for ( int i = 0; i < n; i ++ ) //總共有 n 頁書
27 {
28 scanf ("%d %d", &page[i].ai, &page[i].bi);
29
}
30
31 sort (page, page + n, cmp); //進行排序
32
33
34 //找到最多發送請求的次數: 思路 ：找到第一個end 值之后，通過設定滿足題意的條件 while (i < n && page[i].ai <= sta)
35 //找到新的end 值并且賦值為 j 通過比較 j 和上一次的 end 看看是否得到了新的頁數信息，出口時end == n
36 int count = 1;
37 int sta = page[0].ai;
38 int end = page[0].bi;
39 int j, i = 1;
40
41 while ( i < n && page[i].ai == sta )
42 {
43 if (end < page[i].bi)
44 end = page[i].bi;
45 i ++;
46 }
47
48 while ( end != n )
49 {
50 sta = end + 1;
51 j = page[i].bi;
52 i ++;
53 while (i < n && page[i].ai <= sta) //
54 {
55 if ( page[i].bi > j)
56 {
57 j = page[i].bi; //以最小的覆蓋找到最大的區間長度 ，即 j 保存當前這一組sta 的end
58 }
59 i ++;
60 }
61 if ( j > end )
62 {
63 count ++;
64 end = j;
65 }
66 }
67 printf ("%d\n", count);
68 }
69}
70 // system ("pause");
71 return 0;
72}
73
posted on 2010-08-25 12:14
雪黛依夢 閱讀(2311)
評論(0) 編輯 收藏 引用 所屬分類:
背包----貪心、回溯、分支界限