Description

Input Format

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

Output Format

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

Sample Input 1

5 2
1 2 3 4 5

Sample Output 1

3

Hints

這題目其實是從別的地方偷來的題目
不過被我們修改過 所以變得更難 笑死
n,k3×105 所以別擔心
且保證答案存在 我只能說到這

Subtasks

No. Testdata Range Constraints Score
1 20 範例測資 0
2 0~9 nk1000 20
3 10~19 nk 80

TopCoder

User's AC Ratio

75.0% (3/4)

Tags

Problem Source

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

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