Week 2
2月25日
题目描述
农夫约翰的奶牛们非常爱吃甜食，尤其爱吃拐杖糖。
约翰一共有 N N N 头奶牛，编号 1 ∼ N 1 \sim N 1∼N，其中第 i i i 头奶牛的初始高度为 a i a_i ai。
约翰给奶牛们准备了 M M M 根拐杖糖，编号 1 ∼ M 1 \sim M 1∼M，其中第 i i i 根的高度为 b i b_i bi。
约翰会按照糖果的编号顺序，每次拿出一根糖果喂给奶牛们，直到所有糖果都被喂完为止。
每当拿出一根糖果后，约翰会将其上端固定悬挂，下端自由下垂至刚好接触地面。
然后，奶牛们按照编号顺序，依次走到糖果面前，将糖果自下而上的啃食至自己的高度（因为更高的地方吃不到了）。
由于糖果上端是固定的，所以即使奶牛吃掉糖果的下端部分，糖果也会悬挂在最初设置的位置，不会下降至地面。
当轮到一个奶牛时，如果糖果剩余部分的底部高度已经超过了该奶牛的高度，那么它将什么都吃不到。
在所有奶牛都轮过一次后，不论这根糖果是否被吃完，该糖果都会被约翰扔掉，并换上下一根糖果，继续下一轮次的吃糖（仍然从编号为 1 1 1 的奶牛开始）。
另外，每轮过后，糖果都有可能令奶牛们的身高有所增长，具体为一头奶牛在本轮次吃掉了多少长度的糖果，其身高就会增高多少长度。
请你计算，当所有糖果都喂食完毕后，每头奶牛的最终高度。
输入格式
第一行包含两个整数 N , M N,M N,M。
第二行包含 N N N 个整数 a 1 , a 2 , … , a N a_1,a_2,…,a_N a1,a2,…,aN。
第三行包含 M M M 个整数 b 1 , b 2 , … , b M b_1,b_2,…,b_M b1,b2,…,bM。
输出格式
共 N N N 行，其中第 i i i 行输出第 i i i 头奶牛的最终高度。
数据范围
1 ≤ N , M ≤ 2 × 1 0 5 1 \le N,M \le 2 \times 10^5 1≤N,M≤2×105,
1 ≤ a i , b i ≤ 1 0 9 1 \le a_i,b_i \le 10^9 1≤ai,bi≤109
输入样例：
3 2
3 2 5
6 1
输出样例：
7
2
7
样例解释
第 1 1 1 根糖果的高度为 6 6 6：
- 第 1 1 1 头牛吃掉高度不超过 3 3 3 的部分，糖果剩余部分高度 [ 3 , 6 ] [3,6] [3,6]。
- 第 2 2 2 头牛不够高，吃不到任何糖果。
- 第 3 3 3 头牛吃掉高度不超过 5 5 5 的部分，糖果剩余部分高度 [ 5 , 6 ] [5,6] [5,6]。
第 1 1 1 根糖果喂完，奶牛们的高度变为 [ 3 + 3 , 2 + 0 , 5 + 2 ] = [ 6 , 2 , 7 ] [3+3,2+0,5+2]=[6,2,7] [3+3,2+0,5+2]=[6,2,7]。
第 2 2 2 根糖果的高度为 1 1 1，会被第 1 1 1 头奶牛全部吃掉。
所以，最终奶牛们的高度变为 [ 7 , 2 , 7 ] [7,2,7] [7,2,7]。
解题标签：
暴力模拟 + 剪枝
实现code
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
max_m = 0
for j in range(m):
res = b[j]
max_m = 0
for i in range(n):
if a[i] >= max_m:
diff = min(b[j] - max_m, a[i] - max_m)
max_m = a[i]
a[i] += diff
res -= diff
if res == 0:
break
print("\n".join(map(str, a)))
题目理解
首先，我们需要理解题目的意思：
- 有N头奶牛，每头奶牛有一个初始高度a_i。
- 有M根拐杖糖，每根糖果有一个高度b_i。
- 约翰会按照糖果的编号顺序，依次喂给奶牛们。
- 每根糖果被悬挂，下端接触地面。
- 奶牛们按照编号顺序依次走到糖果面前，啃食糖果至自己的高度。
- 如果糖果的剩余部分底部高度超过了奶牛的高度，奶牛就吃不到糖果。
- 每轮过后，奶牛的身高会增加它们吃掉的糖果长度。
- 最终，我们需要计算每头奶牛的最终高度。
输入输出格式
- 输入：
- 第一行：N和M，表示奶牛和糖果的数量。
- 第二行：N个整数，表示每头奶牛的初始高度。
- 第三行：M个整数，表示每根糖果的高度。
- 输出：
- N行，每行一个整数，表示每头奶牛的最终高度。
数据范围
- 1 ≤ N, M ≤ 2×10^5
- 1 ≤ a_i, b_i ≤ 10^9
样例分析
让我们通过样例来理解题目：
输入样例：
3 2
3 2 5
6 1
输出样例：
7
2
7
解释：
第一根糖果高度为6：
- 第一头奶牛高度为3，吃掉高度0到3的部分，糖果剩余高度为3到6。
- 第二头奶牛高度为2，吃不到糖果。
- 第三头奶牛高度为5，吃掉高度3到5的部分，糖果剩余高度为5到6。
- 第一根糖果喂完后，奶牛们的高度变为[3+3, 2+0, 5+2] = [6, 2, 7]。
第二根糖果高度为1：
- 第一头奶牛高度为6，吃掉整个糖果（高度0到1）。
- 第二头奶牛高度为2，吃不到糖果。
- 第三头奶牛高度为7，吃不到糖果。
- 第二根糖果喂完后，奶牛们的高度变为[6+1, 2+0, 7+0] = [7, 2, 7]。
最终，奶牛们的高度为[7, 2, 7]。
算法思路
我们需要模拟每一根糖果被奶牛们啃食的过程，并更新奶牛的高度。具体步骤如下：
- 对于每一根糖果，初始化其剩余高度为糖果的总高度。
- 按照奶牛的顺序，依次让每头奶牛啃食糖果：
- 如果奶牛的高度大于等于糖果的剩余底部高度，则奶牛可以啃食糖果。
- 计算奶牛可以啃食的糖果长度，并更新奶牛的高度。
- 更新糖果的剩余高度。
- 重复上述过程，直到所有糖果都被喂完。
- 最后输出每头奶牛的最终高度。
代码实现
根据上述思路，我们可以编写如下代码：
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for j in range(m):
res = b[j] # 当前糖果的剩余高度
max_m = 0 # 当前糖果的底部高度
for i in range(n):
if a[i] > max_m:
diff = min(res, a[i] - max_m)
a[i] += diff
max_m += diff
res -= diff
if res == 0:
break
print("\n".join(map(str, a)))
代码解释
输入处理：
- 读取N和M。
- 读取每头奶牛的初始高度a。
- 读取每根糖果的高度b。
模拟过程：
- 对于每一根糖果，初始化剩余高度res为糖果的高度b[j]。
- 初始化糖果的底部高度max_m为0。
- 对于每头奶牛，如果它的高度a[i]大于max_m，则可以啃食糖果。
- 计算可以啃食的长度diff，更新奶牛的高度a[i]和糖果的剩余高度res。
- 更新糖果的底部高度max_m。
- 如果糖果被吃完（res == 0），则跳出循环。
输出结果：
- 输出每头奶牛的最终高度。
END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢