| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 44 | 28 | 18 | 60.000% |
Dabar pats slidinėjimo sezonas! Traukinių stotis ūžia nuo slidinėti važiuojančių poilsiautojų. Bijodami nepavėluoti į traukinį, keleiviai sulipo į vagonus nežiūrėdami, kur yra laisvos vietos.
Kiekviename traukinio vagone yra po K sėdimų vietų, o iš viso traukinyje sėdimų vietų yra lygiai tiek, kiek keleivių – taip jau būna šiuo metų laiku.
Žinodami, kiek keleivių įlipo į kiekvieną iš vagonų, raskite, kiek mažiausiai vagonų keleiviai turės pereiti sumoje, kad kiekvienas keleivis galėtų atsisėsti.
Pirmoje eilutėje pateikiami du sveikieji skaičiai: traukinio vagonų skaičius N ir kiekviename vagone esančių sėdimų vietų skaičius K. Antroje eilutėje pateikta N skaičių ai, kur ai – į i-tąjį vagoną įlipusių keleivių skaičius.
Laikykite, jog a1 + a2 + . . . + aN = N · K.
Išveskite vieną sveikąjį skaičių – kiek mažiausiai vagonų keleiviai turės pereiti sumoje, kad kiekvienas keleivis galėtų atsisėsti.
atsakymas gali būti skaičius viršijantis 32 bitų sveikojo skaičiaus ribas. Atsakymui saugoti naudokite 64 bitų tipo skaičių (long long C/C++, Int64 Pascal).
4 30 0 40 50 30
50
Šiame pavyzdyje traukinį sudaro keturi vagonai, ir kiekviename vagone yra 30 sėdimų vietų. Kad visi galėtų atsisėsti: 10 keleivių turės pereiti iš antrojo vagono į pirmą, 20 keleivių turės pereiti iš trečiojo vagono į pirmą. Taigi iš viso turės būti pereita 1 · 10 + 2 · 20 = 50 vagonų.
Šiuo atveju tai yra efektyviausias sprendimas.