trang chủ / bài tập / weakpoor

Yếu và Nghèo

Cho dãy số nguyên $a_{1}, a_{2}, \dots, a_{n}$ . Hãy tìm một số thực $x$ sao cho độ yếu (weakness) của dãy $a_{1} - x, a_{2} - x, \dots, a_{n} - x$ là nhỏ nhất có thể.

Độ nghèo (poorness) của một đoạn (đoạn con liên tiếp) được định nghĩa là giá trị tuyệt đối của tổng các phần tử trong đoạn đó.

Độ yếu của một dãy được định nghĩa là giá trị lớn nhất của độ nghèo trên tất cả các đoạn của dãy.

Lưu ý: đoạn có thể có độ dài bất kỳ từ $1$ đến $n$ .

Dữ liệu vào

Dòng đầu chứa một số nguyên $n$ — độ dài của dãy.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra một số thực — độ yếu nhỏ nhất có thể đạt được của dãy $a_{1} - x, a_{2} - x, \dots, a_{n} - x$ .

Đáp án được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án chuẩn không vượt quá $10^{- 6}$ .

Ràng buộc

$1 \leq n \leq 200 000$
$| a_{i} | \leq 10 000$

Ví dụ

Input	Output	Giải thích
3 1 2 3	1.000000000	Chọn $x = 2$ , dãy trở thành $- 1, 0, 1$ . Độ nghèo lớn nhất đạt tại đoạn $[- 1]$ hoặc $[1]$ , bằng $1$ .
4 1 2 3 4	2.000000000	Chọn $x = 2, 5$ , dãy trở thành $- 1, 5, - 0, 5, 0, 5, 1, 5$ . Độ nghèo lớn nhất đạt tại đoạn $[- 1, 5, - 0, 5]$ hoặc $[0, 5, 1, 5]$ , bằng $2$ .
10 1 10 2 9 3 8 4 7 5 6	4.500000000	Độ yếu nhỏ nhất đạt giá trị $4, 5$ .

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 7,00một phần

Giới hạn thời gian 2.0s

Python 35.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig