No.3618 Omega Cat (Making ver.)
タグ : / 解いたユーザー数 12
作問者 :
kazuppa
/ テスター :
Problem Statement
$N$ cats are standing in a row. The $i$-th cat is the $i$-th from the left and has height $H_i$. It is guaranteed that the heights of all the cats are pairwise distinct.
You may choose some of these cats and change their heights. The height of a cat after the change can be any non-negative real value.
Find the minimum number of times you need to change a cat's height so that the following condition is satisfied after the changes.
- There exist integers $(x,y,z)$ satisfying all of the following conditions.
- $1< x< y< z< N$
- For every $i$ satisfying $1\leq i< x$, $H_i> H_{i+1}$
- For every $i$ satisfying $x\leq i< y$, $H_i< H_{i+1}$
- For every $i$ satisfying $y\leq i< z$, $H_i> H_{i+1}$
- For every $i$ satisfying $z\leq i< N$, $H_i< H_{i+1}$
You are given $T$ test cases; solve all of them.
Constraints
- $1\leq T\leq 4\times 10^4$
- $5\leq N\leq 2\times 10^5$
- $1\leq H_i\leq 10^9\ (1\leq i\leq N)$
- $H_i\neq H_j\ (i\neq j)$
- The sum of $N$ over all test cases is at most $2\times 10^5$
- All input values are integers
Subtasks
This problem has partial scoring by subtasks.
| Subtask | Points | Constraints |
|---|---|---|
| Subtask 1 | 70 points | $N=5$ |
| Subtask 2 | 70 points | $T\leq 50\ ,N\leq8$ |
| Subtask 3 | 140 points | $N\leq7000,$ the sum of $N$ over all test cases is at most $7000$ |
| Subtask 4 | 70 points | No additional constraints |
Input
$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
Each test case is given in the following format.
$N$ $H_1\ H_2\ \ldots\ H_N$
Output
Print $T$ lines.
On the $i$-th line, print the answer to the $i$-th test case.
Sample
Sample 1
Input
2 7 9 3 4 2 7 6 1 9 9342 314 159 256 2718 1024 1414 169 231
Output
2 1
Consider the $1$-st test case.
For example, changing the $5$-th element to $4$ and the $7$-th element to $6.1$ gives $(9,3,4,2,4,6,6.1)$, which satisfies the condition in the problem statement with $(x,y,z)=(2,3,5)$.
The condition in the problem statement cannot be satisfied with fewer than $2$ changes, so the answer is $2$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。