Zadanie
Nemenovanej spoločnosti sa podarilo navrhnúť dokonalý systém, ako čo najefektívnejšie navrhnúť lety medzi ľubovoľnou skupinou miest tak, aby nebolo treba príliš veľa prestupovať, nemuseli sme chodiť z Bratislavy do Trnavy cez Košice… No, určite si viete aj sami predstaviť mnohé nepríjemnosti, ktoré by mohli nastať, keby lety neboli naplánované rozumne. Čo ale ešte nevymysleli je, že koľko budú stáť jednotlivé lety. Bez veľkého rozmýšľania sa rozhodli priradiť mestám unikátne hodnoty, a cenu letu medzi dvomi mestami určovať ako súčet ich hodnôt. Už teda stačí iba mestám priradiť hodnoty. Lenže ako na to? Hlavným cieľom spoločnosti je samozrejme zarobiť čo najviac. Pomôžte spoločnosti vymyslieť systém ohodnocovania miest tak, aby súčet cien všetkých letov bol čo najväčší.
Úloha
Vašou úlohou bude priradiť \(n\) mestám rôzne hodnoty od \(1\) po \(n\) (vrátane), a to tak, aby súčet cien všetkých letov medzi nimi bol čo najväčší. Cenu letu medzi dvomi mestami vypočítame ako súčet hodnôt daných dvoch miest.
Formát vstupu
Na prvom riadku vstupu sú 2 medzerou oddelené čísla \(n\) a \(m\), kde \(n\) je počet miest a \(m\) je počet letov medzi nimi. Mestá sú očíslované od 0 po \(n-1\). Nasleduje \(m\) riadkov, každý z nich obsahuje 2 medzerou oddelené čísla miest, medzi ktorými sa pravidelne uskutočňujú lety. Rátame s tým, že ak existuje let z A do B, tak existuje aj let z B do A za presne rovnakú cenu, preto s nimi budeme rátať ako s jedným letom a zarátame jeho cenu iba raz (na vstupe nikdy nebude dvojica A B aj B A a taktiež nikdy nebudú na vstupe dva úplne rovnaké lety).
V jednotlivých sadách platia nasledujúce obmedzenia:
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq n \leq\) | \(10\) | \(500\) | \(50000\) | \(100000\) |
\(0 \leq m \leq\) | \(50\) | \(125000\) | \(300000\) | \(500000\) |
Formát výstupu
Vypíšte jediné číslo, a to najväčší možný súčet cien všetkých letov.
Toto číslo môže byť veľké, a teda odporúčame použiť 64 bitovú premennú
(long long
v C++). Nezabudnite za číslom vypísať znak
nového riadku.
Príklady
Input:
3 3
0 1
0 2
1 2
Output:
12
Keď priradíme mestám hodnoty
(mesto:hodnota): 0:1, 1:2, 2:3
, tak potom súčet cien
všetkých letov by bol:
(1 + 2) + (1 + 3) + (2 + 3) = 12
. Môžeme si ale
všimnúť, že v tomto prípade by sme pre ľubovoľné priradenie dostali
rovnaký súčet.
Input:
4 2
0 1
1 2
Output:
13
Pre priradenie: 0:3, 1:4, 2:2, 3:1
získame
takýto súčet: (3 + 4) + (4 + 2) = 13
. Ak by sme
ale zvolili napríklad priradenie: 0:1, 1:2, 2:3, 3:4
,
tak by bol súčet cien všetkých letov menší, a to:
(1 + 2) + (2 + 3) = 8
.
Input:
6 4
0 1
1 2
1 3
2 5
Output:
37
Na začiatok sa pozrime na to, aké informácie vlastne budeme potrebovať. Môžeme si všimnúť, že pre ľubovoľný let \(A\) \(B\) platí, že hodnota mesta \(A\) sa za tento let započíta raz do celkového súčtu cien letov nezávisle od mesta \(B\), rovnako pre mesto \(B\) sa jeho hodnota započíta raz, bez ohľadu na mesto \(A\). Pri zisťovaní celkovej ceny všetkých letov nám teda v skutočnosti nezáleží na tom, medzi ktorými mestami sa uskutočňujú jednotlivé lety, ale iba na tom, koľko existuje letov z jednotlivých miest.
To znamená, že hodnota mesta bude započítaná do celkového súčtu toľkokrát, koľko letov sa z neho uskutočňuje. Preto najväčší možný súčet všetkých letov získame tak, že mestám s najväčším počtom ciest priradíme najväčšie hodnoty.
Vzorové riešenie
Na vyriešenie tejto úlohy nám pri načítavaní vstupu stačí pre každý výskyt nejakého mesta navýšiť počet letov tohto mesta. Následne tieto počty utriedime vzostupne a priradíme mestám v tomto poradí postupne hodnoty od \(1\) po \(n\). Celkový súčet potom dostaneme ako súčet hodnôt priradených mestám vynásobených počtom ich letov.
Keďže si potrebujeme pamätať iba počty letov pre \(n\) miest, tak pamäťová zložitosť bude
\(O(n)\). Načítanie vstupu je v \(O(n + m)\), utriediť pole o veľkosti \(n\) vieme v \(O(n
\cdot \log n)\). Sčítanie celkovej
sumy všetkých letov vieme spraviť v jednom cykle v \(O(n)\). Celková časová zložitosť je teda
\(O(m + n \cdot \log n)\).
= map(int, input().split())
n, m = [0 for _ in range(n)]
pocet_letov
for _ in range(m):
= map(int, input().split())
a, b += 1
pocet_letov[a] += 1
pocet_letov[b]
pocet_letov.sort()= 0
cena_letov for i in range(n):
+= pocet_letov[i] * (i + 1)
cena_letov
print(cena_letov)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
>> n >> m;
cin <int> pocet_letov(n, 0);
vectorfor (int i = 0; i < m; i++)
{
int a, b;
>> a >> b;
cin [a]++;
pocet_letov[b]++;
pocet_letov}
(pocet_letov.begin(), pocet_letov.end());
sortlong long int cena_letov = 0;
for (int i = 0; i < n; i++) cena_letov += pocet_letov[i]*(i+1);
<< cena_letov << endl;
cout return 0;
}
Rýchlejšie riešenie
V skutočnosti ale existovalo aj lepšie riešenie v prípade využitia counting sortu. Ten v prípade, že máme \(k\) hodnôt, ktoré triedime a sú zhora ohraničené nejakou hodnotou \(l\), má časovú zložitosť \(O(k + l)\). V našom prípade máme hodnoty ohraničené pomocou čísla \(m\), keďže ak máme \(m\) letov, tak zo žiadneho mesta nemôže viesť viac ako \(m\) ciest. Preto s použitím counting sortu sa dala táto úloha vyriešiť dokonca v zložitosti \(O(m + n)\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.