canuc80k0018·19/50

Điểm Hẹn Ít Mệt Nhất

Nộp bài trên LQDOJ

Bài 00 · Brute Force

Có người ở các vị trí nguyên . Nếu chọn điểm hẹn nguyên , chi phí của người là . Hãy tìm tổng chi phí nhỏ nhất.

Input

  • Dòng đầu chứa . Dòng thứ hai chứa số nguyên .

Output

  • In giá trị nhỏ nhất của trên mọi số nguyên .

Constraints

  • .
  • .
  • là một số nguyên.

Scoring

  • Subtask ( số điểm): .
  • Subtask ( số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3
1 4 7

Output

18

Giải thích: Chọn cho chi phí . Các vị trí nguyên khác đều cho tổng lớn hơn, nên đáp án là .

Lời giải tóm tắt
  • Ý tưởng: Duyệt P từ 1 đến 100. Với từng vị trí ứng viên, cộng bình phương khoảng cách của mọi người và lấy tổng nhỏ nhất.
  • Chứng minh tính đúng đắn: Một điểm tối ưu không cần nằm ngoài đoạn từ vị trí nhỏ nhất đến lớn nhất, nên miền 1..100 bao phủ mọi ứng viên cần thiết. Thuật toán tính đúng chi phí cho từng ứng viên và lấy nhỏ nhất.
  • Độ phức tạp: O(100N) thời gian và O(N) bộ nhớ.
  • Lỗi cài đặt thường gặp: Dùng trung vị, vốn tối ưu cho tổng khoảng cách tuyệt đối chứ không phải bình phương.
  • Lỗi cài đặt thường gặp: Chỉ thử phần nguyên dưới của trung bình.