SK_001 - Rightful Distribution

 Đọc đề bài trên SPOJ

Tóm tắt: 

Có $n$ học sinh, học sinh thứ $i$ có điểm kiểm tra là $a_i$. Hiệu trưởng muốn chia kẹo cho các em học sinh, sao cho 

• Mỗi em nhận được ít nhất 1 viên kẹo
• Mỗi em nhận được số kẹo nhiều hơn tổng số kẹo của các em điểm thấp hơn em đó.

Tìm số kẹo ít nhất mà hiệu trưởng cần mua để chia cho $n$ em học sinh. Kết quả khá lớn nên mod cho $10^9 + 7$. 

Gợi ý: 

Algoritham. Đừng thấy mod $10^9 + 7$ mà cho rằng bài này kinh khủng.

Hướng dẫn giải:

Gọi $b_i$ là số kẹo chia cho em thứ $i$, $c_i$ là tổng số kẹo cần mua để chia cho $i$ em đầu tiên. Ta sắp xếp mảng $a_i$ thành mảng không giảm. 

Để tổng số kẹo phải chia là ít nhất thì số kẹo chia cho mỗi em phải ít nhất có thể (á à anh hiệu trưởng ki bo bủn xỉn :/), vì vậy ta chia ki bo một chút: các em có điểm bằng nhau sẽ có số kẹo bằng nhau; 2 em hơn điểm nhau mà đứng kề nhau (sau khi sắp xếp điểm) chỉ hơn nhau đúng 1 viên kẹo/

Công thức của $b_i$ lúc đó sẽ là:

$$ \begin{cases} b_i := b_{i - 1} &\text{if $a_i = a_{i - 1}$} \\ b_i := b_{i - 1} + 1 &\text{if $a_i \neq a_{i - 1}$} \end{cases} $$

Cuối cùng là công thức tính tổng: $c_i := c_{i - 1} + b_i \pmod{10^9+7}$. Đáp án sẽ là $c_n$.

Code mẫu (C++).

---

Happy coding!