Xin ý tưởng thuật toán tham lam

#1

mọi người cho em xin ý tưởng bài này với ạ…e cứ loay hoay mãi mà k làm được

Khác với Hiệp sĩ thành Tron, Hiệp sĩ Ba Lan tước đi sự quý phái và hạnh phúc khi giao đấu với nhau. Mỗi hiệp sĩ có một chỉ số sức mạnh và chiến thắng một hiệp sĩ khác khi và chỉ khi sức mạnh của anh ta lớn hơn sức mạnh của đối phương.

Tuy nhiên theo quy định của quốc vương thì mỗi hiệp sĩ được giao đấu với không quá k hiệp sĩ khác. Ngoài ra, mỗi hiệp sĩ có một số lượng tiền. Sau khi chiến thắng đối thủ, một hiệp sĩ có thể giành được tiền thưởng là số tiền của đối thủ.

Bây giờ mỗi hiệp sĩ suy ngẫm: anh ta có thể có bao nhiêu tiền nếu giao đấu với các hiệp sĩ khác. Bạn nên trả lời câu hỏi này cho mỗi hiệp sĩ.

  • Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ min (n - 1, 10)) - số hiệp sĩ và số k.

  • Dòng thứ hai chứa n số nguyên p1, p2, …, pn (1 ≤ pi ≤ 10^9) - sức mạnh của các hiệp sĩ. Sức mạnh của n hiệp sĩ khác nhau từng đôi một.

  • Dòng thứ ba chứa n số nguyên c1, c2, … , cn (0 ≤ ci ≤ 10^9) - số lượng tiền mỗi hiệp sĩ có.

Kết quả : in n số nguyên - số tiền tối đa mà mỗi hiệp sĩ có thể có nếu anh ta giao đấu với tối đa k hiệp sĩ khác.

#2

Sắp xếp các hiệp sĩ theo sức mạnh, nhận xét là theo thứ tự mới thì các hiệp sau luôn có thể đấu các hiệp sĩ phía trước. Vậy duyệt qua từng i, với mỗi i kết quả cho hs đó là tổng k c_j lớn nhất với mọi j < i. Với mỗi i, để tìm tổng k c_j lớn nhất thì có thể duy trì một heap.

6 Likes
#3

em cũng có ý tưởng tương tự vậy nhưng chưa biết thực thi heap như thế nào
nên e duyệt từ đầu đến i-1 để tìm k thằng max thì nó tle
e mới học về heap chưa sâu lắm a cụ thể hơn chút đc ko ạ :3

#4

Max k = 10 nên chắc chắc không TLE.

Max heap (hay priority_queue trong C++) giữ phần tử max ở đỉnh gốc, với mỗi i sau khi xử lí xong thì bỏ c_i vào heap. Vậy với mỗi i, có thể lấy ra k phần tử lớn nhất từ heap. Đpt là O(nklog(n))

Có cách khác hiệu quả hơn, thực hiện trong O(nlogn) không phụ thuộc k sử dụng segment tree.

4 Likes
#5

cám ơn a…em đã làm được rồi

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?