Zadanie

Leto bolo upršané, rastlinám sa darilo. Zvieratá mali čo pod zub, hovnivály kotúľali. Toľko toho nakotúľali, až nevedia, čo s tým. Je im to ľúto len tak všetko prebytočné spláchnuť do záchoda, alebo nechať do ďalšieho leta splesnivieť. Zhodli sa teda, že potrebujú mrazák. Nie ale iba taký obyčajný. Obrovský. Mnohoposchodový.

Rôzne poschodia ale vyžadujú rôzne veľa času na stavbu. Totiž, v niektorých výškach viac fúka, inde je väčšia zima. Hovniválka Elka letmým pohľadom do vzduchu odhadla, koľko času bude potrebného na postavenie ktorého poschodia mrazáku. Konkrétne zistila, že na postavenie \(i\)-teho poschodia bude potrebného \(c_i\) času.

Hovniválka Elka vie, že ak jeden hovnivál buduje guličku \(m\) minút, tisíc hovniválov postaví guličku za \(m/1000\) minút. To, samozrejme, platí aj o stavbe mrazáku. Ak na \(i\)-tom poschodí bude pracovať \(h_i\) hovniválov, tak toto poschodie dokončia za \(c_i/h_i\) času.

Keďže hovnivál má iba také tenké nožičky, rýchlo sa mu unavia. Každý teda zvládne pomôcť postaviť iba jedno poschodie mrazáku. Poschodie sa ale nedá začať stavať, kým nie je dostavané to predchádzajúce, to predsa dá rozum. Hovniválka Elka chce každého z \(H\) hovniválov poslať na práve jedno poschodnie. Chce to spraviť tak, aby bol celkový čas stavania mrazáku čo najkratší.

Ako najrýchlejšie vedia hovnivály postaviť mrazák?

Úloha

Máme \(H\) hovniválov, ktorí chcú postaviť \(n\)-poschodový mrazák. Hovniválka Elka chce priradiť každému z \(H\) hovniválov nejaké poschodie, na ktorom bude pomáhať so stavbou.

Na každom poschodí, samozrejme, musí pracovať aspoň jeden hovnivál.

Ak je na \(i\)-tom poschodí \(h_i\) hovniválov, stavba \(i\)-teho poschodia zaberie \(c_i/h_i\) času.

Vašou úlohou je zistiť, ako najrýchlejšie vie byť mrazák postavený.

Formát vstupu

Na prvom riadku vstupu sú čísla \(n\) – počet poschodí mrazáku a \(H\) – počet hovniválov. Platí, že \(n \leq H\).

Nasleduje \(n\) riadkov. Na \(i\)-tom z nich je číslo \(c_i\) – základný čas potrebný na stavbu \(i\)-teho poschodia. Platí, že \(1 \leq c_i \leq 100\,000\).

Formát výstupu

Vypíšte jedno číslo – najkratší čas, za ktorý je možné mrazák postaviť.

Vaša odpoveď bude uznaná, ak sa od správnej odpovede nebude odlišovať o viac, ako \(1\).

Hodnotenie

Sú 3 sady vstupov. Platia v nich nasledovné obmedzenia:

Sada 1 2 3, 4
\(1 \leq n \leq\) \(8\) \(100\,000\) \(100\,000\)
\(1 \leq H \leq\) \(20\) \(100\,000\) \(10^{12}\)

Príklad

Input:

3 7
6
2
8

Output:

6.667

Snáď ste sa len nenechali zmiasť číslom tejto úlohy. Riešenie je možno jednoduchšie, ako by ste čakali.

Dôležité pozorovanie

Pozrime sa, čo sa stane, ak sme na \(i\)-te poschodie pridali hovnivála. Nech na tom poschodí bolo doteraz \(a_i\) hovniválov. Stavba tohto poschodia by im zabrala \(\frac{c_i}{a_i}\) času. Po pridaní jedného hovnivála im stavba zaberie \(\frac{c_i}{a_i + 1}\) času. Týmto pridaním sme teda ušetrili \(\frac{c_i}{a_i} - \frac{c_i}{a_i + 1} = \frac{c_i}{a_i(a_i + 1)}\).

Môžeme teda rozmiestňovať chrobáky pažravo. Najskôr dáme po jednom na každé poschodie. Následne vždy dáme hovnivála na to poschodie, kde ušetrí najviac času. Toto vieme spraviť v čase \(O(H \log n)\) napríklad pomocou maximovej haldy. V halde budú všetky poschodia a bude utriedená podľa času, ktorý ušetríme pridaním chrobáka na dané poschodie.

Zrýchlenie

Keďže chrobákov je naozaj veľa, potrebujeme niečo zrýchliť. Zaveďme si parameter \(x\). Tento parameter budeme binárne vyhľadávať. Pre \(x\) budeme vedieť zrátať nasledovné. Koľko chrobákov vieme pridávať na poschodia, kým sa náš časový zisk (ten zlomok) stane menší ako \(x\). Budeme chcieť nájsť také \(x\), pre ktoré použijeme \(H\) hovniválov.

Pre poschodie \(i\) vieme zrátať počet hovniválov \(a_i\) na ňom ako \(x = \frac{c_i}{a_i(a_i + 1)}\). Toto vieme vypočítať kvadratickou rovnicou. Keď teda v binárnom vyhľadávaní kontrolujeme dané \(x\), tak prejdeme všetky poschodia. Na každé dáme nanajvýš \(a_i\) hovniválov (tých z kvadratickej rovnice). Ostane nám teda rozmiestniť posledných nanajvýš \(n\). Tých ale vieme doriešiť skôr spomínaným pažravým spôsobom pomocou haldy.

Časová zložitosť tohto riešenia je v závislosti od implementácie zhruba \(O(n(\log C + \log H + \log n))\), kde \(C\) je maximum z \(c_i\). Pamäťová zložitosť je \(O(n)\).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = (int)1e5+5;

ll n, H, c[MAXN];

ll count(double x) {
    ll sum = 0;
    // Pouzijeme kvadraticku rovnicu pre zratanie c[i] / (a_i * (a_i + 1)) >= x
    for (int i = 0; i < n; i++)
        sum += ll((sqrt(1 + 4 * c[i] / x) - 1) / 2);
    return sum;
}

int main() {
    cin >> n >> H;
    H -= n;

    for (int i = 0; i < n; ++i)
        cin >> c[i];

    double lo = 0, hi = 1e18;
    for (int i = 0; i < 200; ++i) {
        double mid = (lo + hi) / 2;
        if (count(mid) >= H)
            lo = mid;
        else
            hi = mid;
    }

    double ans = 0;
    ll sum = 0;

    // Uz vieme zrat x z lo
    // Teraz by sme si mohli zratat pre kazde poschodie, kolko hovnivalov nan mozeme dat pre nase x
    // Ostalo by nam nutne nieco medzi 0 a n hovnivalmi
    // Tych by sme pazravo rozmiestnili na poschodia pomocou haldy.
    // Mame ale aj inu moznost.
    // Ked ak sme pouzili viac, alebo menej chrobakov a mame spravne x, tak staci vhodne upravit zratanu odpoved
    for (int i = 0; i < n; i++) {
        ll x = ll((sqrt(1 + 4 * c[i] / lo) - 1) / 2);
        ans += 1.0 * c[i] / (x + 1);
        sum += x;
    }

    // Od aktualnej odpovede odcitame / pricitame tolko x, kolkych chrobakov mame naviac / menej
    cout << setprecision(9) << fixed << (ans - (H - sum) * lo) << endl;
}

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ť.