偉杰作為銀行的新人會計師,要被迫接手一堆爛攤子
某個工作是這樣的,有個陳年老舊的紙本帳務要做整理
上面有 $n$ 個隨著時間 $i$ 變動的非負數數字 $a_i$,但其中有一些資料怎樣也找不到
偉杰想知道假如這些資料找到後,最大的漲跌變化最小是多少?
但明早會議就得做出一些進度報告了,來不及做一些很好的假設
偉杰只好假定未知數字統一為 $k$ (且精度為 $1$),要使得最大漲跌變化值 $m$ 最小化
這裡 $m$ 就是所有相鄰數字的絕對差值中的最大值,即 $m = \max\limits_{1\le i < n}{|a_i-a_{i+1}|}$
舉例來說,長度 $n = 6$ 的資料為 $a = (?, ?, 9, ?, 3, ?)$,其中 $?$ 代表未知數字
其中一種解 $k = 6$,則資料改為 $a = (6, 6, 9, 6, 3, 6)$,$m = 3$
若是 $k = 1.1$,則資料改為 $a = (1.1, 1.1, 9, 1.1, 3, 1.1)$,$m = 7.9$,這樣就不是偉杰要求的變化值
第一列有個正整數 $n$ 代表資料長度 ($2 \le n \le 5\cdot 10^5$)
第二列有 $n$ 個數字 $a_i$ 表示資料上的數字,其中 $-1$ 為未知數字 ($-1 \le a_i \le 10^9$)
根據題意,資料上已知的數字皆非負數,不會有在 $(-1, 0)$ 中的數字
輸出數字 $m$ 表示最大變化值
浮點數 $m$ 的精度最多只要求小數點後 $1$ 位
第 2 筆範測的 $k$ 為 $2.9$
CODEFORCES 1301B Motarack's Birthday
No. | Testdata Range | Score |
---|---|---|
1 | 0~19 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1500 | 65536 | 65536 | |
1 | 1500 | 65536 | 65536 | |
2 | 1500 | 65536 | 65536 | |
3 | 1500 | 65536 | 65536 | |
4 | 1500 | 65536 | 65536 | |
5 | 1500 | 65536 | 65536 | |
6 | 1500 | 65536 | 65536 | |
7 | 1500 | 65536 | 65536 | |
8 | 1500 | 65536 | 65536 | |
9 | 1500 | 65536 | 65536 | |
10 | 1500 | 65536 | 65536 | |
11 | 1500 | 65536 | 65536 | |
12 | 1500 | 65536 | 65536 | |
13 | 1500 | 65536 | 65536 | |
14 | 1500 | 65536 | 65536 | |
15 | 1500 | 65536 | 65536 | |
16 | 1500 | 65536 | 65536 | |
17 | 1500 | 65536 | 65536 | |
18 | 1500 | 65536 | 65536 | |
19 | 1500 | 65536 | 65536 |