课堂计划 - how to

Problem 1. MooBuzz - S

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

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

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

伪代码:

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

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

13
l, r = 0, int(1e9)
14
while l < r:
15
    mid = l 和 r 的中点
4 collapsed lines
16
    如果 mid 可以
17
        减小 r
18
    否则
19
        增大 l

1
n, m, c = map(int, input().split())
2
li = list(map(int, input().split()))
3
l, r = 0, int(1e9)
4
li.sort()
5
def ok(t):
6
    cnt = 1
7
    st = li[0]
8
    cow = 1
9
    for i in range(1, n):
10
        if li[i] - st > t or cow == c:
11
            cnt += 1
12
            st = li[i]
13
            cow = 1
14
        else:
15
            cow += 1
10 collapsed lines
16
    return cnt <= m
17

18
while l < r:
19
    mid = (l + r) // 2
20
    if ok(mid): # could be smaller
21
        r = mid
22
    else:
23
        l = mid + 1
24

25
print(l)

Problem 2. MooBuzz - S

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

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

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

1
n = int(input()) - 1
2
g = n // 8 # 属于第几组
3
li = [1, 2, 4, 7, 8, 11, 13, 14]
4
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)