Hướng giải của ACM

Hướng dẫn giải

Read the intended approach and key ideas behind this problem.

Hãy nhớ chỉ sử dụng editorial này khi thật sự bị bí, và tuyệt đối không sao chép–dán code từ đó. Hãy tôn trọng tác giả bài toán và người viết lời giải.

Nộp lời giải chính thức trước khi tự mình giải được bài là hành vi có thể bị cấm (ban).

Tác giả: Nguyễn Quang Minh

Tổng quan:
Để tối thiểu hóa số tiền lỗ, 2 bạn sẽ ưu tiên người có mức tiền lỗ nhỏ hơn và cách biệt lớn nhất so với người kia. Vì vậy, ở bài này ta kết hợp sử dụng CTDL Pair và thuật toán Tham lam.

Chi tiết:
* Ta dùng 1 mảng với kiểu pair với phần tử thứ nhất là hiệu của số tiền lỗ của 2 bạn tại ván cược thứ i, phần tử thứ 2 là thứ tự ván cược
* Ta sắp xếp lại theo hiệu và chọn 1 trong 2 bạn vào nửa đầu và bạn kia vào nửa còn lại.

Nhận xét Tham gia thảo luận bên dưới.