ABSMAX
Xem PDF
Điểm:
100
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên \(a_1,a_2,...,a_n\).
Tìm hai chỉ số \(i,j\) thỏa mãn:
- \(i < j\)
- \(|a_i + a_j|\) đạt giá trị lớn nhất
Input
- Dòng đầu ghi số nguyên dương \(n\) \((n \le 200 000)\)
- Dòng sau ghi \(n\) số nguyên \(a_1,a_2,...,a_n\) \((-10^9 \le a_i \le 10^9)\)
Output
- \(\max(|a_i+a_j|)\)
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(n \le 2000\)
- Subtask \(2\) (\(70\%\) số điểm): \(n \le 200 000\)
Example
Test 1
Input
3
1 2 3Output
5
Bình luận
muốn trị của tổng 2 số đạt max thì 2 số đấy phải là 2 số nhỏ nhất hoặc lớn nhất của dãy -> sort tăng dần -> lấy max của trị a[1] + a[2] và trị a[n-1] + a[n]
5 đấm=) lí do 4 sub đầu làm sai đề=))
hmm bài này thì nên dùng jv mn
tag của bài này nên là greedy mới đúng chứ, có thấy toán đâu
test mẫu phải là 5 chứ