Editorial for Bộ sưu tập thẻ

Gọi $S$ ~S~ là tổng số lượng thẻ. Giả sử rằng mỗi giá trị $i$ ~i~ đều được ghi trên ít nhất một tấm thẻ, tức là $A_i \ge 1$ ~A_i \ge 1~ với mọi $1 \le i \le N$ ~1 \le i \le N~. Khi đó, có thể ghép được nhiều nhất $\lfloor\frac{S}{2}\rfloor$ ~\lfloor\frac{S}{2}\rfloor~ cặp thẻ bằng cách như sau:

Sắp xếp tất cả các thẻ theo thứ tự tăng dần giá trị. Khi đó giữa hai tấm thẻ liền kề nhau đều có chênh lệch giá trị tối đa là $1$ ~1~.
Tiến hành ghép các cặp thẻ nằm liền kề nhau.

Quay trở lại với bài toán, từ những giá trị $A_i=0$ ~A_i=0~, ta chia toàn bộ tập thẻ thành các nhóm thẻ riêng biệt (mỗi nhóm thể đều bảo đảm rằng khi sắp xếp các thẻ theo thứ tự tăng dần giá trị, giữa hai tấm thẻ liền kề nhau đều có chênh lệch giá trị tối đa là $1$ ~1~) và tiến hành tính số cặp thẻ tối đa trong từng nhóm này, cuối cùng tổng hợp kết quả.

Độ phức tạp: $O(N)$ ~O(N)~

Editorial for Bộ sưu tập thẻ

Bộ sưu tập thẻ

Comments