A13194. Motarack's Birthday
编程题
普及/提高-
知识点
题目描述
Dark is going to attend Motarack's birthday. Dark decided that the gift he is going to give to Motarack is an array $a$ of $n$ non-negative integers.
Dark created that array $1000$ years ago, so some elements in that array disappeared. Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them. He doesn't have much time so he wants to choose an integer $k$ ( $0 \leq k \leq 10^{9}$ ) and replaces all missing elements in the array $a$ with $k$ .
Let $m$ be the maximum absolute difference between all adjacent elements (i.e. the maximum value of $|a_i - a_{i+1}|$ for all $1 \leq i \leq n - 1$ ) in the array $a$ after Dark replaces all missing elements with $k$ .
Dark should choose an integer $k$ so that $m$ is minimized. Can you help him?
Dark created that array $1000$ years ago, so some elements in that array disappeared. Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them. He doesn't have much time so he wants to choose an integer $k$ ( $0 \leq k \leq 10^{9}$ ) and replaces all missing elements in the array $a$ with $k$ .
Let $m$ be the maximum absolute difference between all adjacent elements (i.e. the maximum value of $|a_i - a_{i+1}|$ for all $1 \leq i \leq n - 1$ ) in the array $a$ after Dark replaces all missing elements with $k$ .
Dark should choose an integer $k$ so that $m$ is minimized. Can you help him?
输入格式
The input consists of multiple test cases. The first line contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains one integer $n$ ( $2 \leq n \leq 10^{5}$ ) — the size of the array $a$ .
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $-1 \leq a_i \leq 10 ^ {9}$ ). If $a_i = -1$ , then the $i$ -th integer is missing. It is guaranteed that at least one integer is missing in every test case.
It is guaranteed, that the sum of $n$ for all test cases does not exceed $4 \cdot 10 ^ {5}$ .
The first line of each test case contains one integer $n$ ( $2 \leq n \leq 10^{5}$ ) — the size of the array $a$ .
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $-1 \leq a_i \leq 10 ^ {9}$ ). If $a_i = -1$ , then the $i$ -th integer is missing. It is guaranteed that at least one integer is missing in every test case.
It is guaranteed, that the sum of $n$ for all test cases does not exceed $4 \cdot 10 ^ {5}$ .
输出格式
Print the answers for each test case in the following format:
You should print two integers, the minimum possible value of $m$ and an integer $k$ ( $0 \leq k \leq 10^{9}$ ) that makes the maximum absolute difference between adjacent elements in the array $a$ equal to $m$ .
Make sure that after replacing all the missing elements with $k$ , the maximum absolute difference between adjacent elements becomes $m$ .
If there is more than one possible $k$ , you can print any of them.
You should print two integers, the minimum possible value of $m$ and an integer $k$ ( $0 \leq k \leq 10^{9}$ ) that makes the maximum absolute difference between adjacent elements in the array $a$ equal to $m$ .
Make sure that after replacing all the missing elements with $k$ , the maximum absolute difference between adjacent elements becomes $m$ .
If there is more than one possible $k$ , you can print any of them.
输入输出样例
输入 #1
7 5 -1 10 -1 12 -1 5 -1 40 35 -1 35 6 -1 -1 9 -1 3 -1 2 -1 -1 2 0 -1 4 1 -1 3 -1 7 1 -1 7 5 2 -1 5
输出 #1
1 11 5 35 3 6 0 42 0 0 1 2 3 4
说明/提示
In the first test case after replacing all missing elements with $11$ the array becomes $[11, 10, 11, 12, 11]$ . The absolute difference between any adjacent elements is $1$ . It is impossible to choose a value of $k$ , such that the absolute difference between any adjacent element will be $\leq 0$ . So, the answer is $1$ .
In the third test case after replacing all missing elements with $6$ the array becomes $[6, 6, 9, 6, 3, 6]$ .
- $|a_1 - a_2| = |6 - 6| = 0$ ;
- $|a_2 - a_3| = |6 - 9| = 3$ ;
- $|a_3 - a_4| = |9 - 6| = 3$ ;
- $|a_4 - a_5| = |6 - 3| = 3$ ;
- $|a_5 - a_6| = |3 - 6| = 3$ .
So, the maximum difference between any adjacent elements is $3$ .
In the third test case after replacing all missing elements with $6$ the array becomes $[6, 6, 9, 6, 3, 6]$ .
- $|a_1 - a_2| = |6 - 6| = 0$ ;
- $|a_2 - a_3| = |6 - 9| = 3$ ;
- $|a_3 - a_4| = |9 - 6| = 3$ ;
- $|a_4 - a_5| = |6 - 3| = 3$ ;
- $|a_5 - a_6| = |3 - 6| = 3$ .
So, the maximum difference between any adjacent elements is $3$ .