课堂计划
2024-10-19
241020julyfunnoteswilliam工作Problem 1. MooBuzz - Shttps://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
否则
增大 ln, 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 - Shttps://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 14n = 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