处理百奇

若初始方向向右，令$s_i=1$，否则令$s_i=0$。类似地，用$c_i$表示最终方向。令$l_i,r_i$分别为第$i$个人向左、向右传递的总次数。方向交替变化，因此$r_i-l_i=s_i-c_i$。

令$P_i=\sum_{j\leq i}A_j$，为扔进左侧垃圾桶的数量。由每条边上的流量守恒，，边界条件为。因此

$$W=\sum_{i=1}^{N}P_i-\sum_{i=1}^{N}s_i,\qquad (N+1)L=W+\sum_{i=1}^{N}c_i.$$

因为$0\leq\sum c_i\leq N$，所以$L=\lceil W/(N+1)\rceil$，最终向右的人数为。

从左到右扫描，维护$l_i$和还需确定的最终向右人数$K$。当$K>0,l_i+s_i\geq1,l_i+s_i-(P_i-L)\geq1$时，取并将减1，否则取。然后计算。答案为。

下面证明贪心选择正确。令$Y_i=\sum_{j\leq i}c_j,H_i=\sum_{j\leq i}s_j,Q_i=\sum_{j\leq i}P_j$，则非负条件等价于

$$Y_i\leq U_i=iL-Q_{i-1}+H_i+\min(0,L-P_i).$$

由于$P_i$单调不减，$U_i$先单调不减，再单调不增，最终等于所需的最终向右人数。因此，只要不超过该总数，尽早选择当前可行的1就不会违反后面的上界。与任意可行最终状态逐个前缀比较，贪心选择1的时刻不会更晚，所以最终一定选择恰好所需数量的1。所有传递次数非负，边界条件也成立。

还需证明这些次数对应合法执行。执行过操作的人的最后一次传递方向与最终方向相反。在路径图上，最后传递方向形成的有向环只能由相邻两人组成，其最终方向依次为左、右。若贪心产生这种转折，则$r_i=0$或$l_{i+1}=0$，从而至少一人从未操作。因此，执行过操作的人之间不存在最后传递方向组成的有向环。

任意合法执行都不能超过计算出的次数：在第一次试图超过某个人的次数时，其邻居传来的数量不超过各自配额，由守恒可知此人没有百奇。反之，若执行结束后仍有未使用的传递配额，这些剩余传递在每个顶点的流入和流出相等，且不会进入垃圾桶。沿剩余的最后一次传递前进必然产生有向环，矛盾。因此所有合法执行的操作次数相同，计算出的和就是最小值。

时间、空间复杂度均为$O(N)$。使用64位有符号整数。令$C=\sum A_i$，由$l_i\leq iC+i-1$可得答案不超过。

Solution written by GPT6.1