Хамгийн Бага Зардалтай Хосууд

2s

512MB

2528

0%

Additional Problems II

$n$ бүхэл тоотой массив өгөгдөнө. $k$ хосоос бүрдэх хослолуудыг авч үзье. Тоо хамгийн ихдээ нэг хосонд ордог ба $(a,b)$ хосын зардал нь $|a-b|$ юм. Хослолын зардал нь хосуудын зардлын нийлбэр.

$k=1,2,\dots,\lfloor n/2 \rfloor$ бүрийн хувьд хослолын хамгийн бага зардлыг ол.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд нэг бүхэл тоо байна: массивын хэмжээ.

Хоёр дахь мөрөнд массивын $n$ бүхэл тоо $x_1,x_2,\dots,x_n$ байна.

Гаралтын формат

$\lfloor n/2 \rfloor$ бүхэл тоо хэвлэ: хослолуудын хамгийн бага зардал.

Хязгаарлалт

$2 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Жишээ

Оролт1

8
3 1 2 7 9 3 4 7

Гаралт1

0 0 1 6

0.1 / 64 KiB

Редактор уншиж байна...