Editorial for Vua Mật Mã
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Có thể giải bài này bằng cách tham lam. Hãy tạo xâu kết quả \(KQ\) bằng cách sau :
\(\quad\) \(\quad\) Bước 1 : Hãy thử từng kí tự \(c\) mà \(cnt_c \geq 1\) theo thứ tự tăng dần của \(c\).
\(\quad\) \(\quad\) Bước 2 : Giả sử ta đã tạo được một số kí tự của xâu \(KQ\), kí tự \(c\) sẽ được chọn nếu \(KQ + c + max \geq S\). \(max\) là xâu kí tự có thứ tự lớn nhất được tạo từ các kí tự còn lại của mảng \(cnt_{char}\).
\(\quad\) \(\quad\) Bước 3 : Sau bước 2, ta đã chọn được kí tự \(c\), nối \(c\) vào \(KQ\), giảm \(cnt_c\) đi 1. Nếu \(KQ > S\), in ra \(KQ\). Nếu \(KQ = S\), quay lại bước 1. Nếu \(KQ < S\), in ra \(-1\).
Comments