[Python_Training] Chi phí thấp nhất 2
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Henry có \(N\) số nguyên \(a_1,a_2,...,a_N\). Mục tiêu của anh ta là làm cho \(N\) số nguyên này bằng nhau thông qua phép biến đổi sau:
- Chọn một số nguyên \(x\) bất kì từ \(N\) số trên và biến số đó thành số nguyên \(y\) với chi phí là \((x-y)^2\) VND (Việt Nam Đồng). (Biết rằng, mỗi số chỉ được chọn không quá \(1\) lần)
Yêu cầu: Tìm tổng chi phí thấp nhất để Henry có thể thực hiện được mục tiêu trên.
Input
- Dòng thứ nhất chứa số nguyên \(N\)
- Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,...,a_N\)
Output
- In ra tổng chi phí thấp nhất cần tìm.
Scoring
- Subtask \(1\) \((30\%)\): \(N \leq 10^2\), \(-10^2 \leq a_i \leq 10^2\).
- Subtask \(2\) \((70\%)\): \(N \leq 10^4\), \(-10^9 \leq a_i \leq 10^9\).
Example
Test 1
Input
3
1 1 3Output
3Note
Giải thích: Anh ấy sẽ đưa tất cả các số trên về giá trị \(2\), do đó tổng chi phí là: \((1-2)^2+(1-2)^2+(3-2)^2=3\)
Bình luận
\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)
\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)
\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)
\(\color{orange}{\text{Hướng dẫn 1}}\)
Hướng dẫn này sẽ áp dụng vào bài chi phí thấp nhất 1
Vì \(|a[i]|<=100\) cho nên các bạn có thể cày trâu từng số để tìm được cách tối ưu
Độ khó:
Gọi \(max(a)\) là số lớn nhất trong dãy, \(min(a)\) là số nhỏ nhất trong dãy:
Độ khó tổng quát là: \(O((max(a)-min(a)+1)*n)\)
\(\color{orange}{\text{Hướng dẫn 2}}\)
Cách làm trong hướng dẫn 1 chỉ là một cách cày trâu, vì thế khi xét các giá trị lớn như trong bài chi phí thấp nhất 2 thì sẽ dễ bị \(TLE\)
Mình xin hướng dẫn chi tiết cho bài chi phí thấp nhất 2 như sau:
Đầu tiên để giải quyết được vấn đề các bạn phải nhận xét được rằng: gọi \(F(x)\) là chi phí để đưa các số về \(x\), thì khi xét \(x\) tăng dần, nó sẽ tạo thành một đồ thị có: Phần đầu giảm chặt, đạt đến giá trị nhỏ nhất, sau đó tăng chặt. (convex)
Nhờ vào đặc tính đó, ta có thể áp dụng chặt tam phân cho bài toán trên. Các bạn có thể xem tại đây
Vậy bài toán sẽ quy về tìm \(F(x)\) nhỏ nhất
Cách làm cụ thể các bạn có thể tham khảo thêm về lý thuyết chặt tam phân nhé! Chúc các bạn accepted!