← 返回题目列表

AtCoder · past202010_i

I. 披萨

中文机器翻译题面 查看原题

分数: 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