OJ 栓奶牛【C】【Python】【二分算法】

题目

算法思路

要求的距离在最近木桩与最远木桩相隔距离到零之间，所以是二分法

先取一个中间值，看按照这个中间值可以栓多少奶牛，再与输入奶牛数比较，如果大于等于，则增大距离，注意这里等于也是增大距离，因为要求的是最大距离，如果这个距离还能再大点呢，如果小于说明距离太大，缩小距离

C代码

//二分法
#include<stdio.h>
int main(){int n,k,p1;scanf("%d %d %d",&n,&k,&p1);int muzhuang[k+1];muzhuang[1]=p1;int i;for(i=2;i<=k;i++){muzhuang[i]=muzhuang[i-1]+((muzhuang[i-1]*2357+137)%10)+1;}int left,right,mid;left=0,right=k;int sum,t,ans;while(left<=right){mid=(left+right)/2;sum=1;t=1;for(i=2;i<=k;i++){if(muzhuang[i]-muzhuang[t]>=mid){t=i;sum++;}}//距离太小,如果等于，则要看看还能不能再大一点if(sum>=n){ans=mid;left=mid+1;}//距离太大else{right=mid-1;}}printf("%d",ans);return 0;
}

Python代码

n, k, p1 = map(int, input().split(' '))
lst = [p1]
for i in range(1, k):lst_i = lst[i - 1] + (lst[i - 1] * 2357 + 137) % 10 + 1lst.append(lst_i)  # 注意防止下标越界
left, right, ans = 0, k - 1, 0
while left <= right:mid = (left + right) // 2  # 注意python不会自动取整sum1, t = 1, 0for i in range(k):if lst[i] - lst[t] >= mid:t = isum1 += 1if sum1 >= n:ans = midleft = mid + 1else:right = mid - 1
print(ans)