3
类似的最大化最小值或者最小化最大值的问题,通常用二分搜索法来解决
我们定义:
C(d): 可以安排牛的最大位置使得最近的两头牛的距离小于d;
那么问题就变成了 求满足C(d)的最大距离d 另外 ,最近的距离4不小于d也可以变成说是所有牛的距离都不小于d,因此就有;
C(d): 可以安排牛的最大位置使得最近的两头牛的距离小于d;
1,对牛舍的位置x进行排序
2把第一头牛放入x0的位置
3,如果第I头牛就要放入满足xj+d<=Xk;
对x 的排序一开始就行了
#include<cstdio> #include<time.h> #include<iostream> #include<algorithm> using namespace std; int n,m; int a[20000]; bool check(int k) { int sum=0; int begin=a[0]; for(int i=1;i<n;i++) { if(a[i]-begin>=k) { sum++; begin=a[i]; } if(sum>=m-1) { return true; } } return false; } void csearch() { sort(a,a+n); int left=0,mid; int right=a[n-1]-a[0]; while(left<=right) { mid=(left+right)/2; if(check(mid)) left=mid; else right=mid; } cout<<left<<endl; } int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; } csearch(); return 0; }