M02456: Aggressive cows

binary search, http://cs101.openjudge.cn/practice/02456

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?

输入

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

* Lines 2..N+1: Line i+1 contains an integer stall location, xi

输出

* Line 1: One integer: the largest minimum distance

样例输入

样例输出

提示

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.

来源: USACO 2005 February Gold

思路是：最大化牛之间的最小间距。

可以二分答案（最小间距 d）。
check(d)：尝试从左到右放牛，如果能放下 C 头牛，则说明 d 可行。
最后得到最大可行的 d。

python

from typing import List

class Solution:
    def maxDistance(self, stalls: List[int], cows: int) -> int:
        stalls.sort()
        
        def can_place(distance: int) -> bool:
            count = 1  # 第一个牛放在第一个stall
            last_pos = stalls[0]
            for pos in stalls[1:]:
                if pos - last_pos >= distance:
                    count += 1
                    last_pos = pos
                    if count >= cows:
                        return True
            return False

        left, right = 1, stalls[-1] - stalls[0] + 1  # 开区间写法
        ans = 0
        while left < right:
            mid = (left + right) // 2
            if can_place(mid):
                ans = mid
                left = mid + 1  # 能放，尝试更大
            else:
                right = mid  # 不能放，缩小范围
        return ans


# 用法示例
if __name__ == "__main__":
    N, C = map(int, input().split())
    stalls = [int(input()) for _ in range(N)]
    sol = Solution()
    print(sol.maxDistance(stalls, C))

python

#蒋子轩23工学院

#判断是否能达到
def can_reach(distance):
    count = 1
    cur = stall[0]
    for i in range(1, n):
        if stall[i] - cur >= distance:
            count += 1
            cur = stall[i]
    return count >= c
#二分查找最大的能达到的距离


def binary_search():
    low = 0
    high = (stall[-1] - stall[0])//(c-1)
    while low <= high:
        mid = (low + high) // 2
        if can_reach(mid):
            low = mid + 1
        else:
            high = mid - 1
    return high


n, c = map(int, input().split())
stall = sorted([int(input()) for _ in range(n)])
print(binary_search())

M02456: Aggressive cows ​

M02456: Aggressive cows