Trò chơi chọn bóng (HSG9 NA 2023)

Điểm: 1500 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 1G

Input: CHONBONG.inp

Output: CHONBONG.out

Tác giả:

Sunlight

Dạng bài

Ngày thành lập Đoàn 26/3 sắp đến. Tuấn cùng nhóm bạn của mình được giao thiết kế một trò chơi trí tuệ dành cho các đoàn viên trong trường. Sau một thời gian tìm hiểu và nghiện cứu, nhóm của Tuấn đã xây dựng một trò chơi có nội dung như sau:

Một rổ bóng có $n$ quả bóng. Các quả bóng được đánh số từ $1$ đến $n$ . Quả bóng thứ $i$ có màu được mã hóa bởi một số nguyên dương $c_i$ ( $1\leq c_i\leq k$ ), trong đó $k$ là số màu khác nhau trong $n$ quả bóng. Mỗi lần chời, người chơi sẽ chọn hai quả bóng khác màu trong rổ bóng và đưa hai quả bóng này ra khỏi rổ. Người chơi sẽ dừng lại khi trong rổ không còn quả bóng nào hoặc không có hai quả bóng khác màu. Số bóng được lấy ra khỏi rổ là số điểm của người chơi.

Tuấn cùng nhóm bạn muốn biết người chơi có thể đạt được điểm lớn nhất là bao nhiêu? Bạn hãy lập trình để tìm kết quả này nhé.

Input, Output và Subtasks

Input: (ChonBong.inp)

Dòng $1$ ghi hai số nguyên $n$ và $k$ ( $2\leq k\leq n\leq 2\times 10^5$ ) tương ứng là số quả bóng trong rổ và số màu khác nhau của $n$ quả bóng.
Dòng $2$ ghi $n$ số nguyên dương $c_1, c_2, ..., c_n$ ( $1\leq c_i\leq k$ ) tương ứng là mã màu của $n$ quả bóng.

Output: (ChonBong.out)

Gồm một số nguyên duy nhất là số điểm lớn nhất người chơi có thể nhận được.

Subtasks

Có $20\%$ số test ứng với $20\%$ số điểm thỏa mãn $2\leq n\leq 2000$ ; $k=2$ .
Có $30\%$ số test ứng với $30\%$ số điểm thỏa mãn $2\leq n\leq 2000$ ; $k=3$ .
Có $30\%$ số test ứng với $30\%$ số điểm thỏa mãn $4\leq n\leq 2000$ ; $3<k\leq n$ .
Có $20\%$ số test ứng với $20\%$ số điểm thỏa mãn $2000<n\leq 2\times 10^5$ ; $3<k\leq n$ .

Sample

Input (ChonBong.inp)

6 2
1 2 2 1 1 1

Output (ChonBong.out)

Notes

Lần $1$ : Chọn quả bóng thứ $1$ và thứ $2$ với mã màu tương ứng là $1$ và $2$ .
Lần $2$ : Chọn quả bóng thứ $3$ và thứ $4$ với mã màu tương ứng là $2$ và $1$ .
Trong rổ bóng lúc này còn $2$ quả thứ $5$ , $6$ đều có mã màu bằng $1$ . Trò chơi kết thúc và người chơi được $4$ điểm. Đây là số điểm cao nhất mà người chơi có thể nhận được.

Sample

Input (ChonBong.inp)

4 3
3 3 1 2

Output (ChonBong.out)

Notes

Lần $1$ : Chọn quả bóng thứ $1$ và thứ $3$ với mã màu tương ứng là $3$ và $1$ .
Lần $2$ : Chọn quả bóng thứ $2$ và thứ $4$ với mã màu tương ứng là $3$ và $2$ .
Trong rổ bóng lúc này không còn quả bóng nào. Trò chơi kết thúc và người chơi được $4$ điểm. Đây là số điểm cao nhất mà người chơi có thể nhận được.

Bình luận

Không có bình luận nào.