44 . 排氣球

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

kenkenken
Caidorz

User's AC Ratio

96.2% (25/26)

Submission's AC Ratio

60.7% (34/56)

Tags

ioicamp ioicamp-2024

Description

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

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

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

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

Input Format

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

輸入第二行有 N 個正整數 a1,a2,…,aN，代表從左邊數過來第 i 顆氣球的顏色。

  • 1≤K≤N≤2×105
  • N2≤K
  • 1≤ai≤K
  • 定義 ci 為陣列 a 中數字 i 出現的次數，則 ∀1≤i≤K,1≤ci≤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

IOICamp 2024 Day5 pB

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，且 a1,a2,…,aK 任兩數字皆不相同 22
5 3, 15~34 N=2K 25
6 0~4, 35~44 N≤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