[USACO17FEB]Why Did the Cow Cross the Road II S 非满分题解代码

以下是一个使用二分答案和贪心算法的 Python 代码实现：

import sys
from math import ceil

def check_speed(speed):
    t = []
    for i in range(n):
        ti = (d[i] - x[i]) / speed
        if ti < 0:
            return False
        t.append(ti)
    t.sort()
    for i in range(n):
        if i > t[i]:
            return False
    return True

n, l = map(int, input().split())
x = list(map(int, input().split()))
d = list(map(int, input().split()))

left, right = 0, 1000000000
while right - left > 0.0001:
    mid = (left + right) / 2
    if check_speed(mid):
        right = mid
    else:
        left = mid

print("{:.2f}".format(left))

其中 check_speed 函数用于检查给定速度是否可行。首先计算每个牛通过道路需要的时间，然后按照时间从小到大排序。对于每个时间，尽可能多地让前面的牛通过道路，然后检查是否还有牛需要等待。如果存在需要等待的牛，则说明当前速度不可行，返回 False。如果所有牛都能够按照给定速度通过道路，则返回 True。

使用二分答案的方法确定速度的范围，然后调用 check_speed 函数检查给定速度是否可行。如果可行，则尝试使用更小的速度。如果不可行，则尝试使用更大的速度。最终，输出最小的速度使得所有牛都能够按照给定速度通过道路。需要注意输出的精度为小数点后两位。