/*求解过程如下：首先对每个区间，以其起始坐标为关键字，从小到大排序。再依次找每查询一次能覆盖
到的最大的区间，假设还没有看过的书页为(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
雪黛依梦 阅读(2255)
评论(0) 编辑 收藏 引用 所属分类:
背包----贪心、回溯、分支界限