课堂计划

Problem 1. MooBuzz - S

https://usaco.org/index.php?page=viewproblem2&cpid=858

二分法复习题。当确定等待上限为 $t$ 时，需要多少辆车可以模拟出来：即时间轴从左往右依次加入奶牛，记录奶牛数量和第一头奶牛的时间，若超时或满载则加一辆。

因此可以二分找到最小的等待上限，若该上限可行则考虑变小，否则变大。

伪代码:

读入 n, m, c 和奶牛时间 li
li 排序

def ok(t):
    初始化变量（自行设计）
    枚举第二头到最后一头奶牛：
        如果超时或者满载：
            换一辆新车
        否则：
            奶牛上车
    返回车数量 <= 车限制

l, r = 0, int(1e9)
while l < r:
    mid = l 和 r 的中点
    如果 mid 可以
        减小 r
    否则
        增大 l

n, m, c = map(int, input().split())
li = list(map(int, input().split()))
l, r = 0, int(1e9)
li.sort()
def ok(t):
    cnt = 1
    st = li[0]
    cow = 1
    for i in range(1, n):
        if li[i] - st > t or cow == c:
            cnt += 1
            st = li[i]
            cow = 1
        else:
            cow += 1
    return cnt <= m

while l < r:
    mid = (l + r) // 2
    if ok(mid): # could be smaller
        r = mid
    else:
        l = mid + 1

print(l)

Problem 2. MooBuzz - S

https://usaco.org/index.php?page=viewproblem2&cpid=966

找规律。每隔 15 个数中，被替代的数字形成一个循环，导致每 15 个数才会报出 8 个数。 最终报的数每过 8 个会增加 15，在 8 个以内则按照下表循环：

0 1 2 3 4 5  6  7
1 2 4 7 8 11 13 14

n = int(input()) - 1
g = n // 8 # 属于第几组
li = [1, 2, 4, 7, 8, 11, 13, 14]
print(g * 15 + li[n % 8])

Problem 3. Problem 1. Marathon

这道题目是一道动规的题目。

令f[i][j]代表到了第i个检查点，跳过了j个的最短距离。

f[i][j]=min(f[i-l-1][j-l]+dis(i,i-l-1))

复杂度为 O(n^3)