Problem B
Utflykt
Languages
en
sv
Inget IOI är komplett utan minst en utflykt. I år ska alla tävlande åka till Cal Orck’o, en arkeologisk utgrävning med dinosauriefotavtryck utanför Sucre. Arrangörerna har skaffat två oändligt stora bussar som ska köra alla deltagare till utgrävningen.
Det finns $N$ deltagare som ska åka på utflykt. Den $i$:te deltagaren är redo att åka vid tid $t_i$. Om en buss avgår vid tid $T$, så kan alla deltagare som uppfyller $t_i \leq T$ åka med bussen. Väntetiden $v_i$ hos deltagare $i$ blir då $T-t_i$.
Din uppgift är att räkna ut den minsta möjliga totala väntetiden $v_1+v_2+\dots +v_N$ om de två bussarnas avgångstider väljs optimalt. Varje deltagare måste åka med en av bussarna, och bussarna kan bara avgå en gång var.
Indata
Den första raden innehåller ett heltal $N$ ($2 \leq N \leq 3 \cdot 10^5$), antalet deltagare.
De $N$ följande raderna innehåller ett heltal $t_i$ ($1 \leq t_i \leq 10^9$) var, tiderna när deltagarna är redo att åka.
Utdata
Skriv ut ett heltal, det minsta möjliga värdet på den totala väntetiden $v_1+v_2+\dots +v_N$.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$17$ |
$N \leq 100$, $t_i \leq 300$ |
|
$2$ |
$26$ |
$N \leq 1000$ |
|
$3$ |
$25$ |
$t_i = i$ för alla $i = 1,2,\dots , N$ |
|
$4$ |
$32$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall
I det första exemplet så är det optimalt att låta de tre första personerna åka med en buss som avgår vid $T = 4$, och de tre sista åker med den andra bussen som avgår vid $T = 11$.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 2 4 1 10 8 11 |
9 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 2025 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
20 1 50000001 100000001 150000001 200000001 250000001 300000001 350000001 400000001 450000001 500000001 550000001 600000001 650000001 700000001 750000001 800000001 850000001 900000001 950000001 |
4500000000 |
