ACM寒假集训——二分

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don’t like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Input

• Line 1: Two space-separated integers: N and C

• Lines 2…N+1: Line i+1 contains an integer stall location, xi
  Output

• Line 1: One integer: the largest minimum distance
  Sample Input
  5 3
  1
  2
  8
  4
  9
  Sample Output
  3
  Hint
  OUTPUT DETAILS:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended.

题目思路：二分的思想就是对半分、平均分，一直对半分到区间为0结束，并且二分法是必须对有序的集合进行。
二分法的重要公式：int mid=(l+r)/2;
二分法的重点在于判断区间，以此题为例：先放一头牛，把他放在a[1]的位置，并用一个变量pos标记每次放牛的位置。如果a[i位置减pos大于等于一半区间，则证明此位置可以放牛，此时更新pos的位置和放牛的数目。
最后判定牛的数目是否大于原先给定的牛的数目，如果大于返回一个真值用于if判断，如果此时满足条件则更新下标，以判定下一个位置是不是满足，不满足更新上标，以判定上一个位置是不是满足，更新时由于上下标的当前位置已经判定过所以可以不必再判定。而且可以根据题目获取你需要得到的上下标的值。

ac代码：
#include<stdio.h>
#include
#include
using namespace std;
const int N=1e5+10;
int a[N];
int m,n;
int judge(int x)
{
int num=1;
int pos=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]-pos>=x)
{
pos=a[i];num++;
}
}
return num>=m;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
int l=0,r=1e9;
int ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(judge(mid))
{
l=mid+1;
ans=mid;
}
else
{
r=mid-1;
}
}
printf("%dn",ans);
return 0;
}

最后

以上就是阳光流沙为你收集整理的ACM寒假集训——二分的全部内容，希望文章能够帮你解决ACM寒假集训——二分所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。