B. 数字清零

    传统题 1000ms 256MiB

数字清零

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

NN 个整数从左向右排成一排,从左到右数第 ii 个整数是 XiX_i。

你可以进行以下操作:

选择位于最右端的 KK 个数,对这 KK 个数全部进行加法(或全部进行减法)运算,要求对于这 KK 个数从左到右数的第 j(1≤j≤K)j (1 ≤ j ≤ K) 个数执行 +j+j (或−j-j)的运算。

你可以操作任意次,每次的 K(1≤K≤N)K (1 ≤ K ≤ N) 值由你决定,每次的运算是全加还是全减也由你决定。

你的目标是把所有数字全部变为 0.

问:你最少需要操作多少次?

输入格式

第一行:一个整数 NN。

第二行:NN 个整数 XiX_i。

输出格式

一个整数,表示最少操作次数。

样例输入

4
0 1 2 -3

样例输出

7

样例解释

初始时:序列 A={0, 1, 2, -3}

第一次操作:K=3,减法:A={0, 1-1=0, 2-2=0, -3-3=-6}={0,0,0,-6}

接下来 6 次操作,每次 K=1,加法,最后全部清零。

数据范围

100% 的数据:1≤N≤2⋅1051 ≤ N ≤ 2·10^5, ∣Xi∣≤1015|X_i|≤ 10^{15},数据保证答案 ≤109≤ 10^9。其中

  • 30% 的数据:N≤103N ≤ 10^3,数据保证答案 ≤103≤ 10^3。
  • 30% 的数据:N≤103N ≤ 10^3,数据保证答案 ≤109≤ 10^9。

2026-03-21-入门级

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-3-21 7:20
结束于
2026-3-21 11:20
持续时间
4 小时
主持人
参赛人数
16