Editorial for Bedao Mini Contest 06 - GIRLS
Submitting an official solution before solving the problem yourself is a bannable offence.
Solution từ
Nhận xét: Đề bài yêu cầu các phần tử được chọn không là liên tiếp nhưng không quan trọng thứ tự ~(i < j)~ thế nên cách tối ưu để chọn là sắp xếp mảng các phân tử tăng dần ~\rightarrow~ Phần tử lớn nhất luôn nằm ở đầu đoạn chọn và phần tử bé nhất luôn nằm ở cuối đoạn chọn.
Qua đó, duy trì một đoạn có độ dài ~[r-N+1, r]~ rồi lấy ~max(sum(r-N+1, r))~ và đoạn duy trì phải thỏa ~a_r - a_{r-N+1} \leq K~. Để tối ưu cách lấy ~sum(r-N+1,r)~ ta có thể sử dụng ~prefix~ ~sum~ để tính trong ~O(1)~.
Solution được đóng góp từ bạn
Ta chỉ cần sắp xếp lại mảng theo giá trị tăng dần, chọn các đoạn ~[l, r]~ gồm ~N~ người và kiểm tra xem đoạn này có thỏa mãn điều kiện ~max(a[l \dots r]) - min(a[l \dots r]) \leq K \Leftrightarrow a[r]-a[l] \leq K~ hay không.
Có thể tính tổng giá trị của một đoạn từ ~l~ đến ~r~ trong ~O(1)~ bằng cách sử dụng mảng cộng dồn.
Mảng cộng dồn được tính theo công thức : ~sum[i] = sum[i-1]+a[i]~ với ~1 \leq i \leq M~ .
Sau khi đã có mảng cộng dồn, tổng giá trị đoạn từ ~l~ đến ~r~ bằng ~sum[r] - sum[l-1]~.
Vậy bài này có thể làm trong ~O(n\ log n)~, trong đó:
~O(n\ log n)~ để sắp xếp
~O(n)~ để dựng mảng cộng dồn
~O(n)~ để duyệt qua các đoạn và cập nhật kết quả
Comments
Idol SPyofgame tuyệt vời quá 😄