【C++基础算法】整数二分答案

整数二分答案

【模板1】：

// 整数二分答案模版

l = a; r = b+1; //初始搜索范围

while(l <= r){

int mid = l + (r-l)/2;

if(judge(mid)){ //满足解的条件

     ans = mid; //记录可行解

     r = mid-1;

}else{

       l = mid+1;

  }  

}

return ans;

题目： 进击的奶牛

题目描述

Farmer John 建造了一个有

（

) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是

（

）。

他的

（

）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

输入格式

第

行：两个用空格隔开的数字

和

。

第

行：每行一个整数，表示每个隔间的坐标。

输出格式

输出只有一行，即相邻两头牛最大的最近距离。

输入输出

输入

5 3

1

2

8

4

9

输出

3

标程

#include<bits/stdc++.h>

usingnamespacestd;

constint N = 1e5 + 10;

int a[N];

int n,c,ans;

// 判断函数

bool judge(int x){//隔间的最小隔间

int num = 1;//第一头牛放第一个隔间

int last = 1;

for(int i = 2; i<= n; i++){

if(a[i] - a[last] >= x){

 num++;

 last = i;

}

}

if(num >= c)return1;//如果牛的数量

else return0;

}

//主函数

int main(){

  scanf("%d%d",&n,&c);

  for(int i = 1; i <= n; i++){

      scanf("%d",&a[i]);

   }

  sort(a+1,a+1+n);

  int l = 1, r = a[n], mid;

  while(l <= r){

   mid = l + (r - l) / 2;// 防止越界 (l+r)>>1

   if (judge(mid)) {

    ans = mid;

    l = mid + 1;

}

else{

 r = mid - 1;

}

}

  cout << ans << endl;

  return 0;

}

相关精彩连接