gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks

二分法
不断枚举一个值,然后根据题目要求判断,这个值与正确答案的大小关系,修改上下界的值,
无穷逼近正确答案,最后就是正确答案

其实我还没有真正了解,通过别人的代码去做的。。。
 1#include <cstdio>
 2#include <algorithm>
 3
 4const int SIZE = 50002 ;
 5
 6int length , N , M ;
 7int distance[SIZE] ;
 8
 9bool Judge(const int& value)
10{
11    int num , i , pre ;
12    num = 0 ;
13    pre = 0 ;
14
15    for ( i = 0 ; i < N ; ++i )
16    {
17        if ( distance[i] - pre < value )
18            num++ ;
19        else
20            pre = distance[i] ;
21    }

22
23    if ( length - pre < value )
24        num++ ;
25
26    if ( num <= M )
27        return true ;
28    else
29        return false ;
30
31    
32}

33
34int BiSearch()
35{
36    int ans = 0 ;
37    int mid , left = 0 , right = length ;
38
39    while ( left <= right )
40    {
41        mid = (left + right) >> 1 ;
42
43        if ( Judge(mid) )
44            left = mid + 1 ;
45        else
46            right = mid - 1 ;
47    }

48
49    ans = left - 1 ;
50
51    return ans ;
52}

53
54int main()
55{
56//    freopen("1.txt", "r", stdin) ;
57
58    int i ;
59    char strNum[12] ;
60
61    scanf("%d %d %d"&length, &N, &M) ;
62    
63    getchar() ;
64    for ( i = 0 ; i < N ; ++i )
65    {
66    //    scanf("%d", &distance[i]) ;
67        gets(strNum) ;
68        distance[i] = atoi(strNum) ;
69    }

70
71    std::sort(distance, distance + N) ;
72
73    printf("%d\n", BiSearch()) ;
74
75    return 0 ;
76}
posted on 2009-03-07 16:03 阅读(354) 评论(0)  编辑 收藏 引用 所属分类: 数学

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理