Chciałbym pokazać wszystkim z klasy, że nie takie OI straszne, jakim go malują ;) Omówię tutaj sposób rozwiązania zadania "Plakatowanie"
które (jak się okazuje) jest w stanie zrobić praktycznie każdy z nas, nawet nie mając wcześniej bliskiego spotkania z programowaniem ;)
Treść zadania znajdziecie pod adresem http://sio.mimuw.edu.pl/user.phtml/pla.pdf?op=get&id=84846
No dobra, ale co nam będzie potrzebne?? Te rzeczy już raczej były na lekcjach ;)
- najważniejsze: mózg ;)
- mieć pojęcie jak mniej więcej działa stos
- umieć tworzyć zmienne "int"
- wiedzieć co to jest "cin" i "cout" ;o
- i najstraszniejsze… pętla for i while
No dobra, to teraz jak się za to zabrać?? Zastanówmy się kiedy plakatów będize najmniej?? Jakimś dziwnym zbiegiem okoliczności
okazuje się, że autor zadania chciał nam namieszać w głowach i wymyślił sobie szerokości budynków. Ale czy są one nam potrzebne??
No… nie za bardzo, skupmy się więc na wysokościach. Rozważmy sobie prosty przykład:
Widzimy, iż domy mają odpowiednio wysokości 2, 3, 2, 5, 4, no dobra, to jakby położyć pierwszy plakat?? Może zróbmy tak, połóżmy
plakat na najmniejszym budynku, bo tak czy siak trzeba go zakleić i chyba najlepiej jednym plakatem, ale zaraz może się zbuntujesz,
mamy 2 domy o wysokości 2!! No to może ten plakat "rozciągniemy" tak, żeby zajął je oba? Tak, to chyba dobry pomysł, ale jak już
tak rozciągamy, to może rozciągnijmy jak się tylko da, czyli na wszystkie?? :) Zawsze to mniejsza powierzchnia potem do zaklejania :)
No to jak tak nakleimy plakat, wyjdzie nam coś takiego:
OK, no to teraz patrząc tylko na to ponad plakatem widzimy, że zostały nam domki o wysokości 0, 1, 0, 3, 2, na ten domek o wys. 1
naklejamy 1 plakat (no bo innej możliwości raczej nie mamy), zostają nam 2 o wys 2 i 3, które jakbyśmy nie kombinowali zakleimy dwoma
plakatami, np naklejając jeden na domek o wys. 2 i "rozciągając go" a potem na resztke ostatniego, a więc wyjdą nam 4 plakaty.
No, fajnie, ale jak to zaklepać?? Możemy szukać za każdym razem najmniejszego domku, odejmować jego wysokość tak jak teraz, a
gdy znajdzie się gdzieś w środku 0 (tak jak u nas 0, 1, 0, 3, 2) rozpatrywać osobno domki oddzielone zerami. Jest jednak problem,
który się zwie złożonością. Jeśli powiedzmy mamy domki w kolejności rosnącej (np. 1, 2, 3, 4, 5), to akurat w tym przypadku musimy
przez tablicę przelecieć 5 razy, a więc wychodzi O(N2), a zgodnie z treścią może być 250 000 domków, co daje 62,5 miliarda
operacji, co zajmie troche ;) Jest jednak szybszy sposób.
Jak to zrobić liniowo(!)? No to tak, spójrzmy na nasz przykład, wczytujemy pierwszą wysokość - 2, zapamiętujemy ją sobie, teraz
zastanówmy się co dalej, jeśli następny dom jest mniejszy, no to trzeba już kleić plakat, bo jakbyśmy się nie starali, to plakatu o
wysokości 2 nie rozciągniemy już nigdzie. A co, jeżeli bedzie taki sam?? A no to nic kompletnie nie robimy ;) A co, jeśli będzie większy??
No cóż, wiemy, że plakat o wysokości 2 go na pewno obejmie, więc zapamiętujemy sobie tą liczbę i szukamy dalej ;)
OK, to konkrety na naszym przykładzie:
- wczytujemy 2, nasza tablica z wysokościami wygląda tak: {2}
- wczytujemy 3, skoro jest większe od 2, to zapamiętujemy je, {2, 3}
- wczytujemy 2, jest mniejsze niż ostatnia liczba (3), więc usuwamy trójeczkę, a co za tym idzie "przyklejamy plakat", nastąpnie porównujemy
dwójkę z dwójką i dziwna rzecz, są takie same, więc już nic nie robimy ;) {2}
- wczytujemy 5, jest większe niż 2, więc dorzucamy ją {2, 5}
- wczytujemy 4, jest mniejsze niż 5, więc usuwamy piątkę "przyklejając plakat". Porównujemy 2 i 4, 2 jest mniejsze, więc dodajemy
czwórkę do tablicy {2, 4}
No i koniec wczytywania, teraz patrzymy ile nam liczb zostało w tablicy. Zostały 2, przykleiliśmy wcześniej 2 plakaty, no to teraz to
sumujemy i wychodzi 2+2=4. Koniec zadanka ;) A to wrzucanie, porównywanie ostatniego i wyrzucanie ostatniego coś ci przypomina??
Tak, to jest stos :) A teraz straszliwie długi i skomplikowany kod w C++ jak to zaklepać :)
#include <iostream> using namespace std; int main() { int tab[250000], n, liczba, i=0, plakaty=0, szer; //tab ma 250000 komórek, bo tyle może być domów cin >> n >> szer >> tab[0]; // wczytujemy liczbę domów a następnie wymiary pierwszego z nich for (int a=1; a<n; a++) //pętelka, która wczyta resztę :) { cin >> szer >> liczba; //wczytujemy wymiary domku while (liczba<tab[i]) //jeżeli dom jest mniejszy niż poprzedni, to zrzucamy domki ze stosu, aż snajdziemy mniejszy lub równy { plakaty++; //za każdym razem jak coś zrzucimy "naklejamy plakat" i--; //zmniejszamy też wskaźnik, który pokazuje na ostatnie zajęte miejsce na stosie if (i==-1) tab[++i]=liczba; //a jeśli stos się opróżni (i==-1) to trzeba liczbe zapisać do tab[0] } if (liczba>tab[i]) //jeśli domek jest większy niż ostatni na stosie, to wrzucamy go na stos tab[++i]=liczba; } plakaty+=i+1; //dodajemy ilość domków na stosie do ilości plakatów cout << plakaty << endl; return 0; }
Tak, wiem, że stos nie jest piękny i na lekcji był ładniejszy, ale wtedy gdy to pisałem nie wiedziałem nawet, że istnieje coś takiego jak stos i po prostu taki pomysł się zjawił ;)
Pytanie czy to działa?? Wygląda na to, że niestety tak ;) Jeśli wierzyć sprawdzarce szkolnej Olimp by mib & earl
..::OLIMP::..
Automagiczna testerka binarek
(C) Mib & Earl
Testowanie rozwiązania zadania Plakatowanie
+--------------------------------------+
| 0 | 191 OK | Answer correct |
| 1 | 17 OK | Answer correct |
| 2 | 23 OK | Answer correct |
| 3 | 23 OK | Answer correct |
| 4 | 125 OK | Answer correct |
| 5 | 189 OK | Answer correct |
| 6 | 19 OK | Answer correct |
| 7 | 17 OK | Answer correct |
| 8 | 16 OK | Answer correct |
| 9 | 16 OK | Answer correct |
| 10 | 16 OK | Answer correct |
| 11 | 17 OK | Answer correct |
| 12 | 16 OK | Answer correct |
| 13 | 16 OK | Answer correct |
| 14 | 16 OK | Answer correct |
| 15 | 16 OK | Answer correct |
| 16 | 184 OK | Answer correct |
| 17 | 115 OK | Answer correct |
| 18 | 161 OK | Answer correct |
| 19 | 15 OK | Answer correct |
| 20 | 16 OK | Answer correct |
| 21 | 16 OK | Answer correct |
| 22 | 16 OK | Answer correct |
| 23 | 31 OK | Answer correct |
| 24 | 24 OK | Answer correct |
| 25 | 16 OK | Answer correct |
| 26 | 20 OK | Answer correct |
| 27 | 28 OK | Answer correct |
| 28 | 31 OK | Answer correct |
| 29 | 21 OK | Answer correct |
| 30 | 28 OK | Answer correct |
| 31 | 23 OK | Answer correct |
| 32 | 32 OK | Answer correct |
| 33 | 149 OK | Answer correct |
| 34 | 15 OK | Answer correct |
| 35 | 16 OK | Answer correct |
| 36 | 16 OK | Answer correct |
| 37 | 16 OK | Answer correct |
| 38 | 17 OK | Answer correct |
| 39 | 17 OK | Answer correct |
| 40 | 16 OK | Answer correct |
| 41 | 16 OK | Answer correct |
| 42 | 16 OK | Answer correct |
| 43 | 22 OK | Answer correct |
| 44 | 16 OK | Answer correct |
| 45 | 16 OK | Answer correct |
| 46 | 16 OK | Answer correct |
| 47 | 16 OK | Answer correct |
| 48 | 17 OK | Answer correct |
| 49 | 17 OK | Answer correct |
| 50 | 16 OK | Answer correct |
| 51 | 16 OK | Answer correct |
| 52 | 16 OK | Answer correct |
| 53 | 17 OK | Answer correct |
| 54 | 16 OK | Answer correct |
| 55 | 18 OK | Answer correct |
| 56 | 16 OK | Answer correct |
| 57 | 16 OK | Answer correct |
| 58 | 16 OK | Answer correct |
| 59 | 16 OK | Answer correct |
| 60 | 18 OK | Answer correct |
| 61 | 16 OK | Answer correct |
| 62 | 16 OK | Answer correct |
| 63 | 17 OK | Answer correct |
| 64 | 16 OK | Answer correct |
| 65 | 25 OK | Answer correct |
| 66 | 15 OK | Answer correct |
| 67 | 16 OK | Answer correct |
| 68 | 16 OK | Answer correct |
| 69 | 16 OK | Answer correct |
+-----------------------+--------------+
| Statystyki |
+-----------------------+--------------+
| Poprawnych: | 70 |
| Błędnych odpowiedzi: | 0 |
| Poza limitem czasu: | 0 |
| Błędów wykonania: | 0 |
+-----------------------+--------------+
| Czas wykonania |
+-----------------------+--------------+
| Sumaryczny [ms] | 2258 |
| Najdłuzszy [ms] | 191 |
| Średni [ms] | 32 |
+-----------------------+--------------+
| Punkty | 100 |
+-----------------------+--------------+
Dla porównania rozwiązanie kwadratowe wspomniane na samym początku:
+--------------------------------------+
| 0 | 43 OK | Answer correct |
| 1 | 17 OK | Answer correct |
| 2 | 16 OK | Answer correct |
| 3 | 23 OK | Answer correct |
| 4 | 579 OK | Answer correct |
| 5 | 2086 TL | Time limit exceeded |
| 6 | 26 OK | Answer correct |
| 7 | 19 OK | Answer correct |
| 8 | 17 OK | Answer correct |
| 9 | 16 OK | Answer correct |
| 10 | 16 OK | Answer correct |
| 11 | 17 OK | Answer correct |
| 12 | 17 OK | Answer correct |
| 13 | 16 OK | Answer correct |
| 14 | 18 OK | Answer correct |
| 15 | 17 OK | Answer correct |
| 16 | 674 OK | Answer correct |
| 17 | 309 OK | Answer correct |
| 18 | 816 OK | Answer correct |
| 19 | 16 OK | Answer correct |
| 20 | 17 OK | Answer correct |
| 21 | 21 OK | Answer correct |
| 22 | 37 OK | Answer correct |
| 23 | 65 OK | Answer correct |
| 24 | 46 OK | Answer correct |
| 25 | 24 OK | Answer correct |
| 26 | 44 OK | Answer correct |
| 27 | 96 OK | Answer correct |
| 28 | 51 OK | Answer correct |
| 29 | 34 OK | Answer correct |
| 30 | 67 OK | Answer correct |
| 31 | 38 OK | Answer correct |
| 32 | 68 OK | Answer correct |
| 33 | 503 OK | Answer correct |
| 34 | 25 OK | Answer correct |
| 35 | 16 OK | Answer correct |
| 36 | 15 OK | Answer correct |
| 37 | 17 OK | Answer correct |
| 38 | 16 OK | Answer correct |
| 39 | 17 OK | Answer correct |
| 40 | 20 OK | Answer correct |
| 41 | 19 OK | Answer correct |
| 42 | 20 OK | Answer correct |
| 43 | 23 OK | Answer correct |
| 44 | 17 OK | Answer correct |
| 45 | 18 OK | Answer correct |
| 46 | 17 OK | Answer correct |
| 47 | 19 OK | Answer correct |
| 48 | 18 OK | Answer correct |
| 49 | 19 OK | Answer correct |
| 50 | 18 OK | Answer correct |
| 51 | 21 OK | Answer correct |
| 52 | 16 OK | Answer correct |
| 53 | 16 OK | Answer correct |
| 54 | 15 OK | Answer correct |
| 55 | 48 OK | Answer correct |
| 56 | 19 OK | Answer correct |
| 57 | 52 OK | Answer correct |
| 58 | 20 OK | Answer correct |
| 59 | 20 OK | Answer correct |
| 60 | 23 OK | Answer correct |
| 61 | 24 OK | Answer correct |
| 62 | 24 OK | Answer correct |
| 63 | 24 OK | Answer correct |
| 64 | 20 OK | Answer correct |
| 65 | 19 OK | Answer correct |
| 66 | 21 OK | Answer correct |
| 67 | 24 OK | Answer correct |
| 68 | 40 OK | Answer correct |
| 69 | 28 OK | Answer correct |
+-----------------------+--------------+
| Statystyki |
+-----------------------+--------------+
| Poprawnych: | 69 |
| Błędnych odpowiedzi: | 0 |
| Poza limitem czasu: | 1 |
| Błędów wykonania: | 0 |
+-----------------------+--------------+
| Czas wykonania |
+-----------------------+--------------+
| Sumaryczny [ms] | 4571 |
| Najdłuzszy [ms] | 816 |
| Średni [ms] | 65 |
+-----------------------+--------------+
| Punkty | 98 |
+-----------------------+--------------+
