为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 319329
  • 排名 - 75

最新评论

阅读排行榜

评论排行榜

#include <iostream>
#include 
<algorithm>
#include 
<vector>
#include 
<string>
using namespace std;
#define MAXSIZE 100010
int x[MAXSIZE];
int c,n;
bool check(int dis)
{
    
int pre=0,count=1;
    
for(int i=1;i<n;i++)
        
if(x[i]-x[pre]>=dis)
        {
            count
++;
            
if(count>=c) return 1;
            pre
=i;
        }
    
return 0;
}
int binary_search()
{
    
int low=0,up=x[n-1]-x[0],mid;
    
while(low<up)
    {
        
//mid=low+(up-low)/2;
        mid=(low+up+1)/2;
        
if(check(mid))
            low
=mid;
        
else up=mid-1;
    }
    
return low;
}
int main()
{
    scanf(
"%d%d",&n,&c);
    
for(int i=0;i<n;i++)
        scanf(
"%d",&x[i]);
    sort(x,x
+n);
    printf(
"%d\n",binary_search());
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=2456

注意二分时mid的取值
posted on 2009-09-09 23:44 baby-fly 阅读(301) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

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