30/09/2018, 23:13
Mọi người cho mình xin thuật toán của bài này..mình suy nghĩ nhưng ko biết làm thế nào
"Diện tích " của một chuỗi được mô tả như sau:
ví dụ: abbcdacb
a: 2 lần
b: 3 lần
c: 2 lần
d 1 lần
Diện tích là: 22+33+22+11=18
Cho một chuỗi s và một số k bất kì.Viết hàm loại bỏ k lần một kí tự từ chuỗi s sao cho diện tích của chuỗi s là min
Ví dụ trong chuỗi s ở trên nếu k =3 thì
Diện tích nhỏ nhất là: 11+11+22+11=7
(a mất 1 lần,b mất 2 lần)
Bài liên quan
Tìm số lần xuất hiện lớn nhất của một kí tự nào đó rồi trừ đi 1. Lặp lại k lần như vậy. Đây chỉ là ý tưởng ban đầu, bạn có thề suy nghĩ thêm để optimize nó.
Trước tiên tìm toàn bộ số lần các kí tự trong dãy. xét xem cái nào lớn nhất. sau đó xét k và số lượng kí tự cao nhất.
Nếu k nhỏ hơn thì giảm kí tự đó đi k lần.
Nếu k lớn hơn thì giảm kí tự đó đi về còn 1 lần. và sau đó k sẽ còn là k- số lượng kí tự đó. rồi xét tiếp đến kí tự lớn thứ 2 rồi làm tương tự
Lấy ví dụ dãy s=abbcdacb
Mảng đếm có dc T={a:2,b:3,c:2,d:1}
V là diện tích của chuỗi
Để Vmin thì mỗi lần xoá, ta xoá đi chữ số nào có nhiều nhất. bởi nếu a>b thì
a*a-(a-1)*(a-1)>b*b-(b-1)*(b-1)là độ chênh lệch V(min) sau khi xoá. Như vậy bạn phải làm dc 2 việc:-tìm max(mảng đếm), cập nhật lại giá trị đó
-cập nhật lại V
Bạn dùng priority_queue cho việc 1. Từ đó có thể cập nhật kết quả việc 2 dễ dàng