AT_jsc2023_final_e.Min Subtraction

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\cdots,A_N)$ 。

你可以任意次（可以为 $0$ 次）重复如下操作：

选择一个整数 $i$ （ $1 \leq i \leq N-1$ ），令 $v=\min(A_i,A_{i+1})$ 。将 $A_i$ 变为 $A_i-v$ ， $A_{i+1}$ 变为 $A_{i+1}-v$ 。

请你求经过操作后， $A$ 中 $0$ 的个数的最大值。

输入格式

输入通过标准输入以以下格式给出。

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请输出答案。

输入输出样例

输入#1
```
4
1 2 1 2
```
输出#1
```
3
```
输入#2
```
5
1 1 1 1 1
```
输出#2
```
4
```
输入#3
```
6
6 5 4 3 2 1
```
输出#3
```
5
```

输入#4

20
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

输出#4

说明/提示

样例解释 1

可以按如下方式进行操作。

在 $i=1$ 处操作后， $A=(0,1,1,2)$ 。
在 $i=2$ 处操作后， $A=(0,0,0,2)$ 。

此时， $A$ 中包含 $3$ 个 $0$ 。无法使 $A$ 中包含 $4$ 个 $0$ ，因此答案为 $3$ 。

数据范围

$2 \leq N \leq 250000$
$1 \leq A_i \leq 10^9$
所有输入的数均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页