首页 > 代码库 > NOJ---1567---二分查找
NOJ---1567---二分查找
这题我的代码 还没有在OJ上提交 因为 我们的Oj 又崩溃了=-=
touch me
=他好了 就去交了 但应该是对的了 因为 大神帮我解决了那个死循环问题
l = mid+1 与 l = mid
在某种严格意义上来说还是不同的 当我的条件是---mid = (l+r)/2 那么它是偏向L的 写法就应该采用第一种
如果mid = ( l + r + 1 )/2 那么r应写为mid-1
这题的二分还是不难的
二分的基本框架还是差不多的 主要是binarysearch的写法
这个还是要看具体的题目 =-=
1 #include <iostream> 2 using namespace std; 3 4 int n , m; 5 const int size = 500010; 6 int arr[size]; 7 8 bool bSearch( int x ) 9 {10 int cnt;11 cnt = 0;12 for( int i = 0 ; i<n ; i++ )13 {14 cnt += ( arr[i] + (x - 1) ) / x;15 }16 return cnt<=m;17 }18 19 int main()20 {21 int l , r;22 int mmax;23 while( ~scanf("%d %d",&n,&m) )24 {25 mmax = 0;26 if( n==-1 && m==-1 )27 break;28 for( int i = 0 ; i<n ; i++ )29 {30 scanf( "%d",&arr[i] );31 if( arr[i]>mmax )32 {33 mmax = arr[i];34 }35 }36 l = 0;37 r = mmax;38 while( l<r )39 {40 int mid = l+(r-l)/2;41 if( bSearch(mid) )42 {43 r = mid;44 }45 else46 {47 l = mid+1; 48 }49 }50 cout<<l<<endl;51 }52 return 0;53 }
today:
I don’t know if we each have a destiny , or just floating around—like on a breeze
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。