分数: 6 点
警告
2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
你今天的晚餐是披萨。 有 N 披萨片,已编号 1 通过 N,按此顺序顺时针排列。 注意那一块 N 和一块 1 彼此相邻。
片的美味 i is a_i.
你将选择一些连续的块并吃掉它们。 例如,如果披萨有 10 件,可以选择件 8,9,10,1,2 并吃掉它们,但无法选择 1,3,5.
找到以下的最小可能值 |X-Y| 其中 X 和 Y 分别是您吃掉的部分和剩余部分的美味程度之和。
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 2 \times 10^5
- 1 \leq a_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N a_1 \cdots a_N
输出
打印最小可能值 |X-Y| 其中 X 和 Y 分别是您吃掉的部分和剩余部分的美味程度之和。
示例输入 1
4 10 20 40 30
示例输出 1
20
- 一个最佳选择是选择吃掉碎片 4,1,2.
- 在这里,你吃的每一片美味的总和, X是 30+10+20=60,以及剩余的部分, Y是 40,导致 |X-Y|=20.
- 请注意,既不选择棋子 1,3 也不选择 允许使用 2,4 ,因为这些棋子组不是连续的。
示例输入 2
20 13 76 46 15 50 98 93 77 31 43 84 90 6 24 14 37 73 29 43 9
示例输出 2
1