Bài toán lập trình chia tập hợp

Pham_Thanh_Duy · May 15, 2022, 10:36am

Mình ko nghĩ ra được cách làm bài này ạ. Nếu xét theo kiểu chọn hết các trường hợp có thể sắp xếp thành 2 nhóm thì lại nhiều trường hợp quá mà nếu mình cố tìm cách lược bớt thì lại bị xót trường hợp. Mong mọi người chỉ giáo ạ. Mình cảm ơn nhiều ạ!

rogp10 · July 22, 2021, 2:02am

Số dương thì dùng nhánh cận thôi nhưng n lớn hơn 50 thì chỉ có sort lại rồi greedy.

Pham_Thanh_Duy · July 22, 2021, 2:31am

sort với greedy là j vậy bạn. Mk hơi kém khoản này

rogp10 · July 22, 2021, 2:58am

Greedy bài này tức là duy trì |hiệu số| nhỏ nhất giữa dãy chọn và dãy không chọn, bằng cách tạo các cặp số.

Pham_Thanh_Duy · July 22, 2021, 3:14am

bài này cần chia cả tập số đó thành 2 rồi tính hiệu của 2 tập số mới được lập ra nhưng mk đang ko biết cách để chia tập số đó thành 2 ấy

MR.QD · July 22, 2021, 8:40am

Bạn tham khảo link bài viết này xem nhé

rogp10 · July 22, 2021, 9:17am

Cái này là giải bài cơ bản thêm điều kiện số phần tử thì ko đc.

Sau khi sort thì lấy hai phần tử chỉ số chẵn lẻ là 1 cặp, mỗi cặp chọn đúng 1 phần tử theo cách greedy là giữ chênh lệch thấp hơn.