Milk Exchange

题目描述

农夫约翰的 $N$ 头奶牛（$1 \leq N \leq 5 \cdot 10^5$）围成一个圆圈排队。 第 $i$ 头奶牛有一个容量为整数 $a_i$（$1 \leq a_i \leq 10^9$）升的桶。所有桶起初都是满的。

每过一分钟，对于 $1\le i<N$，奶牛 $i$ 会把自己桶里的所有牛奶都传给奶牛 $i+1$，而奶牛 $N$ 会把牛奶传给奶牛 $1$。所有交换同时发生（也就是说，如果一头奶牛的桶是满的，她给出 $x$ 升牛奶的同时也收到 $x$ 升，那么她的牛奶会被保留）。如果某头奶牛的总牛奶量曾经超过 $a_i$，则超出的牛奶会丢失。

在经过 $1, 2, \dots, N$ 分钟后，所有奶牛的牛奶总量各是多少？

输入格式

第一行包含 $N$。 下一行包含整数 $a_1,a_2,...,a_N$。

输出格式

输出 $N$ 行，其中第 $i$ 行为经过 $i$ 分钟后所有奶牛剩余的牛奶总量。

6
2 2 2 1 2 1

8
7
6
6
6
6

8
3 8 6 4 8 3 8 1

25
20
17
14
12
10
8
8

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

2000000053
1000000054
56
49
42
35
28
24
20
20

提示

初始时，每个桶中的牛奶量为 $[2, 2, 2, 1, 2, 1]$。 经过 $1$ 分钟后，每个桶中的牛奶量为 $[1, 2, 2, 1, 1, 1]$，因此牛奶总量为 $8$。 经过 $2$ 分钟后，每个桶中的牛奶量为 $[1, 1, 2, 1, 1, 1]$，因此牛奶总量为 $7$。 经过 $3$ 分钟后，每个桶中的牛奶量为 $[1, 1, 1, 1, 1, 1]$，因此牛奶总量为 $6$。 经过 $4$ 分钟后，每个桶中的牛奶量为 $[1, 1, 1, 1, 1, 1]$，因此牛奶总量为 $6$。 经过 $5$ 分钟后，每个桶中的牛奶量为 $[1, 1, 1, 1, 1, 1]$，因此牛奶总量为 $6$。 经过 $6$ 分钟后，每个桶中的牛奶量为 $[1, 1, 1, 1, 1, 1]$，因此牛奶总量为 $6$。 经过 $1$ 分钟后，每个桶中的牛奶量为 $[1, 3, 6, 4, 4, 3, 3, 1]$，因此牛奶总量为 $25$。 计分： 输入 4-5：$N \le 2000$ 输入 6-8：$a_i \le 2$ 输入 9-13：所有 $a_i$ 在区间 $[1,10^9]$ 内均匀随机生成。 输入 14-23：无额外限制。 题目贡献者：Chongtian Ma, Alex Liang, Patrick Deng

标签: USACO|2024|Gold

来源

USACO|2024|Gold