309727: CF1725L. Lemper Cooking Competition

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Lemper Cooking Competition

题意翻译

有一个序列,可以进行若干次操作。 在每一次操作里,他可以选择第 $i$ 个元素($ 2 \le i \le N-1$),然后执行以下操作: 1. 把 $ A_{i-1}$ 变为 $A_{i-1} + A_{i}$。 2. 把 $ A_{i+1}$ 变为 $A_{i+1} + A_{i}$。 3. 把 $A_i$ 变为 $-A_i$。 现在让你求执行的最少操作次数,以使序列的元素值都处于非负值。 如果无解,请输出 $-1$ 。

题目描述

Pak Chanek is participating in a lemper cooking competition. In the competition, Pak Chanek has to cook lempers with $ N $ stoves that are arranged sequentially from stove $ 1 $ to stove $ N $ . Initially, stove $ i $ has a temperature of $ A_i $ degrees. A stove can have a negative temperature. Pak Chanek realises that, in order for his lempers to be cooked, he needs to keep the temperature of each stove at a non-negative value. To make it happen, Pak Chanek can do zero or more operations. In one operation, Pak Chanek chooses one stove $ i $ with $ 2 \leq i \leq N-1 $ , then: 1. changes the temperature of stove $ i-1 $ into $ A_{i-1} := A_{i-1} + A_{i} $ , 2. changes the temperature of stove $ i+1 $ into $ A_{i+1} := A_{i+1} + A_{i} $ , and 3. changes the temperature of stove $ i $ into $ A_i := -A_i $ . Pak Chanek wants to know the minimum number of operations he needs to do such that the temperatures of all stoves are at non-negative values. Help Pak Chanek by telling him the minimum number of operations needed or by reporting if it is not possible to do.

输入输出格式

输入格式


The first line contains a single integer $ N $ ( $ 1 \le N \le 10^5 $ ) — the number of stoves. The second line contains $ N $ integers $ A_1, A_2, \ldots, A_N $ ( $ -10^9 \leq A_i \leq 10^9 $ ) — the initial temperatures of the stoves.

输出格式


Output an integer representing the minimum number of operations needed to make the temperatures of all stoves at non-negative values or output $ -1 $ if it is not possible.

输入输出样例

输入样例 #1

7
2 -1 -1 5 2 -2 9

输出样例 #1

4

输入样例 #2

5
-1 -2 -3 -4 -5

输出样例 #2

-1

说明

For the first example, a sequence of operations that can be done is as follows: - Pak Chanek does an operation to stove $ 3 $ , $ A = [2, -2, 1, 4, 2, -2, 9] $ . - Pak Chanek does an operation to stove $ 2 $ , $ A = [0, 2, -1, 4, 2, -2, 9] $ . - Pak Chanek does an operation to stove $ 3 $ , $ A = [0, 1, 1, 3, 2, -2, 9] $ . - Pak Chanek does an operation to stove $ 6 $ , $ A = [0, 1, 1, 3, 0, 2, 7] $ . There is no other sequence of operations such that the number of operations needed is fewer than $ 4 $ .

Input

题意翻译

有一个序列,可以进行若干次操作。 在每一次操作里,他可以选择第 $i$ 个元素($ 2 \le i \le N-1$),然后执行以下操作: 1. 把 $ A_{i-1}$ 变为 $A_{i-1} + A_{i}$。 2. 把 $ A_{i+1}$ 变为 $A_{i+1} + A_{i}$。 3. 把 $A_i$ 变为 $-A_i$。 现在让你求执行的最少操作次数,以使序列的元素值都处于非负值。 如果无解,请输出 $-1$ 。

Output

**题目大意:**
有一个炉子序列,每个炉子有一个初始温度值,可能为负。可以进行多次操作,每次操作可以选择一个特定的炉子(非最左或最右边的炉子),然后:
1. 将其左侧炉子的温度增加到当前炉子温度。
2. 将其右侧炉子的温度增加到当前炉子温度。
3. 将当前炉子的温度取反。

目标是使得所有炉子的温度都变为非负值。求实现这一目标所需的最少操作次数。如果不能实现,输出-1。

**输入输出数据格式:**
- **输入格式:**
- 第一行包含一个整数 $ N $($ 1 \le N \le 10^5 $),表示炉子的数量。
- 第二行包含 $ N $ 个整数 $ A_1, A_2, \ldots, A_N $($ -10^9 \leq A_i \leq 10^9 $),分别表示每个炉子的初始温度。
- **输出格式:**
- 输出一个整数,表示所需的最少操作次数,如果不能实现则输出-1。**题目大意:** 有一个炉子序列,每个炉子有一个初始温度值,可能为负。可以进行多次操作,每次操作可以选择一个特定的炉子(非最左或最右边的炉子),然后: 1. 将其左侧炉子的温度增加到当前炉子温度。 2. 将其右侧炉子的温度增加到当前炉子温度。 3. 将当前炉子的温度取反。 目标是使得所有炉子的温度都变为非负值。求实现这一目标所需的最少操作次数。如果不能实现,输出-1。 **输入输出数据格式:** - **输入格式:** - 第一行包含一个整数 $ N $($ 1 \le N \le 10^5 $),表示炉子的数量。 - 第二行包含 $ N $ 个整数 $ A_1, A_2, \ldots, A_N $($ -10^9 \leq A_i \leq 10^9 $),分别表示每个炉子的初始温度。 - **输出格式:** - 输出一个整数,表示所需的最少操作次数,如果不能实现则输出-1。

加入题单

上一题 下一题 算法标签: