/*求解过程如下:首先对每个区间,以其起始坐标为关键字,从小到大排序。再依次找每查询一次能覆盖
到的最大的区间,假设还没有看过的书页为(sta , end),每次可以查询的小段区间用(xi , yi) 表示,
那么对于没有找过的每段区间,我们都是找 xi<=sta,并且yi > sta的区间中yi最大的区间,直到yi = end为止。
最后统计区间的个数,即为最少的查询次数。*/
1
#include <iostream>
2
#include <algorithm>
3
using namespace std;
4
#include <string.h>
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
struct book
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
8
int ai;
9
int bi;
10
}page[5001];
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
bool cmp (const book &a, const book &b)
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
14
return a.ai < b.ai;
15
}
16
int main ()
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
18
int t, n;
19
while ( scanf ("%d", &t) != EOF )
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
21
for ( int i = 0; i < t; i ++ ) //t 组测试数据
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
23
24
memset (page, 0, sizeof (page));
25
scanf ("%d", &n);
26
for ( int i = 0; i < n; i ++ ) //总共有 n 页书
27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
43
if (end < page[i].bi)
44
end = page[i].bi;
45
i ++;
46
}
47
48
while ( end != n )
49![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
50
sta = end + 1;
51
j = page[i].bi;
52
i ++;
53
while (i < n && page[i].ai <= sta) //
54![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
55
if ( page[i].bi > j)
56![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
57
j = page[i].bi; //以最小的覆盖找到最大的区间长度 ,即 j 保存当前这一组sta 的end
58
}
59
i ++;
60
}
61
if ( j > end )
62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
63
count ++;
64
end = j;
65
}
66
}
67
printf ("%d\n", count);
68
}
69
}
70
// system ("pause");
71
return 0;
72
}
73![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2010-08-25 12:14
雪黛依梦 阅读(2265)
评论(0) 编辑 收藏 引用 所属分类:
背包----贪心、回溯、分支界限