Độ khó chịu
Xem PDF
Điểm:
900 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1\), \(A_2\),..., \(A_N\), ta định nghĩa độ khó chịu của một đoạn con \([L, R]\) là giá trị \(\max(A[L], A[L+1],..., A[R])-\min(A[L], A[L+1],..., A[R])\). Hãy lập trình xác định đoạn con có độ khó chịu nhỏ nhất trong số các đoạn con \([L, R]\) với \(1\leq L < R\leq N\) của dãy \(A\).
Input
- Dòng đầu chứa số nguyên dương \(N\) \((2\leq N\leq 10^5)\).
- Dòng thứ hai chứa \(N\) số nguyên mô tả dãy \(A\). Các số đều có giá trị tuyệt đối không vượt quá \(10^9\).
Output
- Một số nguyên là độ khó chịu nhỏ nhất tìm được.
Example
Test 1
Input
2
1 3Output
2Test 2
Input
3
1 1 1Output
0Test 3
Input
5
1 2 1 2 1Output
1Note
Ở ví dụ cuối cùng, đoạn con tối ưu ta có thể chọn là \([1, 5]\), giá trị lớn nhất và nhỏ nhất của đoạn con này lần lượt là \(1\) và \(2\), ta được độ khó chịu bằng \(2-1=1\).
Kỳ thi:
- TKPC - Song Sư vs Tam Kiệt (12 Tháng 8., 2021)
Bình luận