Phân tích: Text Messaging Outrage

Đây là một trong những bài toán dễ nhất của Vòng 1. Chúng ta chỉ cần lấp đầy bàn phím điện thoại một cách tham lam. Chúng ta đặt \(K\) chữ cái có tần suất xuất hiện nhiều nhất vào vị trí đầu tiên của \(K\) phím, \(K\) chữ cái có tần suất nhiều tiếp theo vào vị trí thứ hai, và cứ tiếp tục như vậy. Bất kỳ giải pháp tối ưu nào cũng sẽ có cấu trúc này, bởi vì nếu không, nó có thể được cải thiện bằng cách tráo đổi một ký tự có tần suất lớn hơn ở vị trí có chỉ số cao hơn của một phím nào đó với một ký tự có tần suất nhỏ hơn ở vị trí có chỉ số thấp hơn, từ đó làm giảm tổng số lần nhấn phím.

Cách cài đặt

Dưới đây là mã nguồn thực hiện giải pháp này:

long long A[1000];

int main() {
  int N;
  cin >> N;
  for(int t = 1; t <= N; t++) {
    long long result = 0;
    int P, K, L;
    cin >> P >> K >> L;
    for(int i = 0; i < L; i++) cin >> A[i];
    sort(A, A+L);
    reverse(A, A+L);

    for(int i = 0; i < L; i++)
      result += (1 + i / K) * A[i];

    cout << "Case #" << t << ": " << result << endl;
  }
}

Độ phức tạp

• Thời gian: \(O(L \log L)\) để sắp xếp tần suất của các chữ cái, sau đó là \(O(L)\) để tính tổng số lần nhấn phím.
• Không gian: \(O(L)\) để lưu trữ tần suất của các chữ cái.

Dựa trên phân tích chính thức của Google Code Jam.