A15600 | The Human Equation
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Petya and his friend, the robot Petya++, went to BFDMONCON, where the costume contest is taking place today.
While walking through the festival, they came across a scientific stand named after Professor Oak and Golfball, where they were asked to solve an interesting problem.
Given a sequence of numbers $a_1, a_2, \dots, a_n$ you can perform several operations on this sequence.
Each operation should look as follows. You choose some subsequence $^\dagger$ . Then you call all the numbers at odd positions in this subsequence northern, and all the numbers at even positions in this subsequence southern. In this case, only the position of the number in the subsequence is taken into account, not in the original sequence.
For example, consider the sequence $1, 4, 2, 8, 5, 7, 3, 6, 9$ and its subsequence (shown in bold) $1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$ . Then the numbers $4$ and $5$ are northern, and the numbers $2$ and $6$ are southern.
After that, you can do one of the following:
- add $1$ to all northern numbers and subtract $1$ from all south numbers; or
- add $1$ to all southern numbers and subtract $1$ from all northern numbers.
Thus, from the sequence $1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$ , if you choose the subsequence shown in bold, you can get either $1, \mathbf{5}, \mathbf{1}, 8, \mathbf{6}, 7, 3, \mathbf{5}, 9$ or $1, \mathbf{3}, \mathbf{3}, 8, \mathbf{4}, 7, 3, \mathbf{7}, 9$ .
Then the operation ends. Note also that all operations are independent, i. e. the numbers are no longer called northern or southern when one operation ends.
It is necessary to turn all the numbers of the sequence into zeros using the operations described above. Since there is very little time left before the costume contest, the friends want to know, what is the minimum number of operations required for this.
The friends were unable to solve this problem, so can you help them?
$^\dagger$ A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) elements.
While walking through the festival, they came across a scientific stand named after Professor Oak and Golfball, where they were asked to solve an interesting problem.
Given a sequence of numbers $a_1, a_2, \dots, a_n$ you can perform several operations on this sequence.
Each operation should look as follows. You choose some subsequence $^\dagger$ . Then you call all the numbers at odd positions in this subsequence northern, and all the numbers at even positions in this subsequence southern. In this case, only the position of the number in the subsequence is taken into account, not in the original sequence.
For example, consider the sequence $1, 4, 2, 8, 5, 7, 3, 6, 9$ and its subsequence (shown in bold) $1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$ . Then the numbers $4$ and $5$ are northern, and the numbers $2$ and $6$ are southern.
After that, you can do one of the following:
- add $1$ to all northern numbers and subtract $1$ from all south numbers; or
- add $1$ to all southern numbers and subtract $1$ from all northern numbers.
Thus, from the sequence $1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$ , if you choose the subsequence shown in bold, you can get either $1, \mathbf{5}, \mathbf{1}, 8, \mathbf{6}, 7, 3, \mathbf{5}, 9$ or $1, \mathbf{3}, \mathbf{3}, 8, \mathbf{4}, 7, 3, \mathbf{7}, 9$ .
Then the operation ends. Note also that all operations are independent, i. e. the numbers are no longer called northern or southern when one operation ends.
It is necessary to turn all the numbers of the sequence into zeros using the operations described above. Since there is very little time left before the costume contest, the friends want to know, what is the minimum number of operations required for this.
The friends were unable to solve this problem, so can you help them?
$^\dagger$ A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) elements.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.
The first line of each test case contains an integer $n$ ( $1 \le n \le 2\cdot 10^5$ ) — the length of the sequence.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $-10^9 \le a_i \le 10^9$ ) — the description of the sequence itself.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$ .
The first line of each test case contains an integer $n$ ( $1 \le n \le 2\cdot 10^5$ ) — the length of the sequence.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $-10^9 \le a_i \le 10^9$ ) — the description of the sequence itself.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$ .
输出格式
For each test case, print one integer in a single line — the minimum number of operations it takes to turn all the numbers into zeros.
输入输出样例
输入 #1
5 3 1 2 -3 5 1 0 0 -1 -1 6 2 -4 3 -5 4 1 5 1 -1 1 -1 1 7 0 0 0 0 0 0 0
输出 #1
3 2 6 1 0
In the first test case, the sequence of operations is as follows: $\mathbf{1}, 2, \mathbf{-3} \longrightarrow 0, \mathbf{2}, \mathbf{-2} \longrightarrow 0, \mathbf{1}, \mathbf{-1} \longrightarrow 0, 0, 0$ .
In the second test case, the sequence looks like this: $\mathbf{1}, 0, 0, \mathbf{-1}, -1 \longrightarrow 0, 0, 0, 0, \mathbf{-1} \longrightarrow 0, 0, 0, 0, 0$ .
In the fourth test case, simply select the entire sequence as a subsequence, then subtract one from the northern numbers and add one to the southern numbers. Thus, the sequence will be nulled in one operation.
In the fifth test case, you don't need to do any operations, since the sequence already consists of zeros.
In the second test case, the sequence looks like this: $\mathbf{1}, 0, 0, \mathbf{-1}, -1 \longrightarrow 0, 0, 0, 0, \mathbf{-1} \longrightarrow 0, 0, 0, 0, 0$ .
In the fourth test case, simply select the entire sequence as a subsequence, then subtract one from the northern numbers and add one to the southern numbers. Thus, the sequence will be nulled in one operation.
In the fifth test case, you don't need to do any operations, since the sequence already consists of zeros.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted