Traukinys
시간 제한1초메모리 제한1024 MB
N개의 객차에 각각 K개의 좌석이 있고 승객 수가 주어질 때, 모든 승객이 앉기 위해 객차 사이를 이동하는 최소 총 횟수를 구한다.
문제
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).
제한
- 1 ≤ N ≤ 1 000 000
- 1 ≤ K ≤ 1 000 000