#include // Načteme "magickou hlavičku", která načte celou standardní knihovnu using namespace std; int main(void) { int N, K; // N je počet loutek, K nosnost věšáku // Odkomentuj následující řádek, pokud chceš, aby program místo ze // standardního vstupu četl vstup ze souboru "vstup.in" v aktuálním // adresáři: // freopen("vstup.in", "r", stdin); cin >> N >> K; // Načteme vstup ze standardního vstupu // Pořídíme si pole čísel velikosti N, na začátku vyplněné samými nulami vector w(N); // w, neboli weights, neboli hmotnosti loutek for (int i = 0; i < N; i++) cin >> w[i]; // Postupně do pole načteme vstup (čímž přepíšeme nuly) // pole si předzvětšit potřebujeme, jinak by mělo nulovou velikost a // cin >> w[i] by se snažilo psát za konec (nulového) pole a program by // nefungoval (a nejspíš by spadl) // Seřadíme loutky vzestupně podle hmotnosti, to trvá O(N log N) času sort(w.begin(), w.end()); // Trik oproti algoritmu popisovaném ve vzorovém řešení: nejen, že nebudeme // provádět mazání zleva a místo toho si budeme pamatovat ukazatel na // nejlevější "nesmazaný" prvek (left), my nebudeme mazat ani zprava (a budeme si // pamatovat right, ukazatel na nejpravější nezmazaný prvek) int left = 0, right = N - 1; // na začátku pracujeme s celým polem int vesaku = 0; // Počet použitých věšáků // Během celého průběhu algoritmu platí, že nepověšené jsou loutky s vahami // w[left], w[left + 1], ..., w[right], všechny ostatní už jsou pověšené while (left <= right) { // Zkoumáme, s čím pověsíme loutku na pozici `right` if (w[left] + w[right] <= K) // Pokud se k ní nejlehčí loutka vejde left++; // "Smažeme" ji right--; // Vždy pověsíme aspoň tu pravou, "smažeme" ji z pole vesaku++; // Ať tak nebo tak, použili jsme další věšák } cout << vesaku << "\n"; }