C. Ачаалал тэнцвэржүүлэх

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сургуулийн компьютерийн өрөөнд хэд хэдэн тооцоолох ажлуудыг ажиллуулж чадах $n$ сервер байна. Та сервер бүрийн хувьд хуваарилагдсан ажлын тоог мэднэ: энд $i$-р серверт $m_{i}$ ширхэг ажил ноогдсон байна.

Сервер бүрийн хувьд ачааллыг тэнцвэржүүлэхийн тулд та хамгийн ачаалалтай сервер ба хамгийн ачаалал багатай серверийн ялгааг боломжит хамгийн бага байлгахаар дахин хуваарилахыг хүсэж байна. Өөрөөр хэлбэл та $m_{a} - m_{b}$ илэрхийллийг хамгийн бага байлгахыг хүсэж байгаа ба энд $a$ нь хамгийн ачаалалтай сервер ба $b$ нь хамгийн бага ачаалалтай сервер юм.

Нэг секундэд та нэг ажлыг дахин хуваарилаж чадна. Иймээс нэг секундэд та дурын хос серверийг сонгож нэг ажлыг нэгээс нь нөгөөд шилжүүлж чадна.

Серверүүлийн ачааллыг тэнцвэржүүлэхэд хамгийн багадаа хэдэн секунд шаардлагатайг олох програм бич.

Оролт

Эхний мөрөнд эерэг тоо $n$ ($1 ≤ n ≤ 10^{5}$) байх ба серверүүдийн тоо юм.

Хоёр дахь мөрөнд эерэг бүхэл тоон утгын дараалал $m_{1}, m_{2}, ..., m_{n}$ ($0 ≤ m_{i} ≤ 2*10^{4}$) байх ба энд $m_{i}$ нь $i$-р серверт хуваарилагдсан ажлуудын тоо байна.

Гаралт

Ачааллыг тэнцвэржүүлэхэд шаардлагатай секундыг илэрхийлэх хамгийн бага тоог хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
2
1 6
Гаралт
2
Оролт
7
10 11 10 11 10 11 11
Гаралт
0
Оролт
5
1 2 3 4 5
Гаралт
3

Тэмдэглэл

Эхний жишээн дээр хоёр секунд хэрэгтэй. Секунд бүрт нэг ширхэг ажил #2 серверээс #1 серверрүү зөөгдөнө. Хоёр секундын дараа #1 сервер дээр 3 ажил #2 сервер дээр 4 ажил болох ёстой.

Хоёр дахь жишээн дээр ачаалал аль хэдийн тэнцвэржчихсэн байна.

Гурав дахь жишээний хувьд ажил шилжүүлэх боломжит дараалал нь:

  1. #4 серверээс #1 серверрүү нэг ажил зөөнө ($m$-н дараалал: 2 2 3 3 5 болно);
  2. #5 серверээс #1 серверрүү нэг ажил зөөнө ($m$-н дараалал: 3 2 3 3 4 болно);
  3. #5 серверээс #2 серверрүү нэг ажил зөөнө ($m$-н дараалал: 3 3 3 3 3 болно);

Дээрх дараалал нь серверүүдийн ачааллыг гурван секундэд тэнцвэржүүлэх боломжит хэд хэдэн аргын нэг юм.

Сэтгэгдлүүдийг ачааллаж байна...