Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
A. Мафи
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
$n$ хүн "мафи" тоглоомыг тоглохоор цугларав. Үе болгонд нэг нь зохицуулагч хийж бусад $n-1$ нь тоглоомонд оролцоно. Хүн болгон тоглоомын хэдэн үед нь зохицуулагч биш оролцож тоглохыг хүсэж байгаагаа хэлжээ. Бүх тоглогчийн хувьд хүссэн тооноос нь багагүйгээр оролцогч байлгаж болох хамгийн бага тоглолтын үеийн тоог ол.
Оролт
Эхний мөрөнд $n$ тоо ($3 ≤ n ≤ 10^5$). Хоёр дахь мөрөнд $n$ ширхэг тоо $a_1$, $a_2$, ... , $a_n$ ($1 ≤ a_i ≤ 10^9$) байрлана. $a_i$ нь $i$ дахь тоглогчийн хамгийн багадаа оролцогч байж үзэхийг хүсэж байгаа үеийн тоо.
Гаралт
Нэг мөрөнд хүн бүрийг ядаж $a_i$ удаа оролцуулахын тулд хамгийн багадаа шаардагдах тоглолтын тоо.
C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d эсвэл cin, cout стриймийг ашиглана уу.
Орчуулсан: gmunkhbaatarmn
Жишээ тэстүүд
Оролт
3 3 2 2
Гаралт
4
Оролт
4 2 2 2 2
Гаралт
3
Тэмдэглэл
You don't need to know the rules of "Mafia" to solve this problem. If you're curious, it's a game Russia got from the Soviet times: http://en.wikipedia.org/wiki/Mafia_(party_game)$.