44 . 排氣球

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

kenkenken
Caidorz

User's AC Ratio

100.0% (25/25)

Submission's AC Ratio

61.8% (34/55)

Tags

ioicamp ioicamp-2024

Description

又到了一年一度的氣球嘉年華，在佈置場地時，小桃在桌子上將 $N$ 顆氣球排成一列，其中從左邊數來第 $i$ 顆氣球有顏色 $a_i$。這些氣球一共有 $K$ 種顏色，而且為了避免顏色太單調，每一種顏色的氣球至多只有兩顆。

在小桃擺放完畢後，小櫻走了過來檢查，但她覺得這樣的氣球排列方式不好看，她認為需要滿足以下條件才是好看的：

  • 對於所有有兩顆氣球的顏色，兩氣球之間需至少有 $K - 1$ 顆氣球

為了讓氣球變好看，小櫻每次可以選擇兩個相鄰的氣球，並將它們交換。但因為小櫻還要忙著去檢查其他場地，她希望能越快處理完越好。她想請問你她最少需要進行幾次交換才能滿足她的需求，你能幫幫她嗎？

Input Format

輸入第一行有兩個正整數 $N, K$，代表氣球的數量以及氣球的顏色數量。

輸入第二行有 $N$ 個正整數 $a_1, a_2, \ldots, a_N$，代表從左邊數過來第 $i$ 顆氣球的顏色。

  • $1 \leq K \leq N \leq 2 \times 10^ 5$
  • $\frac{N}{2} \leq K$
  • $1 \leq a_i \leq K$
  • 定義 $c_i$ 為陣列 $a$ 中數字 $i$ 出現的次數，則 $\forall 1 \leq i \leq K, 1 \leq c_i \leq 2$

Output Format

請輸出一行，該行有一個整數，代表小櫻最少需要進行的交換次數。

Sample Input 1

5 3
3 2 1 1 2

Sample Output 1

3

Sample Input 2

5 4
2 3 1 4 1

Sample Output 2

2

Sample Input 3

10 5
1 5 3 2 4 2 4 3 1 5

Sample Output 3

8

Sample Input 4

10 5
4 1 5 5 2 4 3 2 1 3

Sample Output 4

6

Sample Input 5

17 10
5 6 5 6 2 1 9 10 4 3 8 2 1 9 8 3 7

Sample Output 5

26

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~4 範例測資 0
2 5~9 $N = K$ 3
3 1, 10~14 $N = K + 1$ 7
4 2, 15~24 $N = 2K$，且 $a_1, a_2, \ldots, a_K$ 任兩數字皆不相同 22
5 3, 15~34 $N = 2K$ 25
6 0~4, 35~44 $N \leq 2000$ 12
7 0~64 無其他限制 31

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 6 7
1 2000 524288 65536 1 3 6 7
2 2000 524288 65536 1 4 6 7
3 2000 524288 65536 1 5 6 7
4 2000 524288 65536 1 6 7
5 2000 524288 65536 2 7
6 2000 524288 65536 2 7
7 2000 524288 65536 2 7
8 2000 524288 65536 2 7
9 2000 524288 65536 2 7
10 2000 524288 65536 3 7
11 2000 524288 65536 3 7
12 2000 524288 65536 3 7
13 2000 524288 65536 3 7
14 2000 524288 65536 3 7
15 2000 524288 65536 4 5 7
16 2000 524288 65536 4 5 7
17 2000 524288 65536 4 5 7
18 2000 524288 65536 4 5 7
19 2000 524288 65536 4 5 7
20 2000 524288 65536 4 5 7
21 2000 524288 65536 4 5 7
22 2000 524288 65536 4 5 7
23 2000 524288 65536 4 5 7
24 2000 524288 65536 4 5 7
25 2000 524288 65536 5 7
26 2000 524288 65536 5 7
27 2000 524288 65536 5 7
28 2000 524288 65536 5 7
29 2000 524288 65536 5 7
30 2000 524288 65536 5 7
31 2000 524288 65536 5 7
32 2000 524288 65536 5 7
33 2000 524288 65536 5 7
34 2000 524288 65536 5 7
35 2000 524288 65536 6 7
36 2000 524288 65536 6 7
37 2000 524288 65536 6 7
38 2000 524288 65536 6 7
39 2000 524288 65536 6 7
40 2000 524288 65536 6 7
41 2000 524288 65536 6 7
42 2000 524288 65536 6 7
43 2000 524288 65536 6 7
44 2000 524288 65536 6 7
45 2000 524288 65536 7
46 2000 524288 65536 7
47 2000 524288 65536 7
48 2000 524288 65536 7
49 2000 524288 65536 7
50 2000 524288 65536 7
51 2000 524288 65536 7
52 2000 524288 65536 7
53 2000 524288 65536 7
54 2000 524288 65536 7
55 2000 524288 65536 7
56 2000 524288 65536 7
57 2000 524288 65536 7
58 2000 524288 65536 7
59 2000 524288 65536 7
60 2000 524288 65536 7
61 2000 524288 65536 7
62 2000 524288 65536 7
63 2000 524288 65536 7
64 2000 524288 65536 7
Submit
Back to Top