Bài toán gồm 2 phần:

Phần 1: Tính số kẹo ở hộp cuối cùng

Đáp số là tổng số kẹo trong tất cả hộp

Phần 2: Tính thời gian

Nếu làm theo đề bài thì mỗi lần gộp kẹo xong, ta phải sắp xếp lại các hộp kẹo. Nếu sử dụng thuật toán bình thường thì sẽ là \(O(n^2)\) hoặc \(O(n^2\log)\)

Ta có thể cải tiến để làm nó nhanh hơn bằng cách sử dụng các cấu trúc dữ liệu cao cấp hơn như multiset hay priority_queue. Các CTDL này cho phép các thao tác sau:

• Thêm một số vào tập hợp trong \(O(\log)\)
• Tìm số nhỏ nhất trong \(O(\log)\)
• Xóa số nhỏ nhất trong \(O(\log)\)

Chẳng hạn dưới đây là code cho priority_queue.

priority_queue<int, vector<int>, greater<int>> pq; // C++
for i = 1 .. n
  pq.push(a[i])
while !pq.empty():
  smallest = pq.top() // tìm số nhỏ nhất
  pq.pop() // xóa số nhỏ nhất
  second_smallest = pq.top() // tìm số nhỏ nhất
  pq.pop() // xóa số nhỏ nhất
  new_box = smallest + second_smallest
  time += new_box
  pq.push(new_box) // thêm hộp kẹo mới vào

Làm theo cách trên, độ phức tạp là \(O(n\log n)\)