Author |
Message |
06/11/2018 18:33:46
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
http://mendo.mk/algoritmi/Task.do?competition=150&id=673
Ja resiv so slednoto:
Ama 100000% sum siguren deka ne e vaka nameneta da se resi...
Kako e nameneta da se resi?
|
|
|
06/11/2018 22:49:35
|
жучко
Joined: 28/06/2016 17:52:08
Messages: 9
Offline
|
Treba da se koristat 2 heaps i sliding window, tako sto edniot heap gi cuva broevite pomali ili ednakvi na medijanata a drugiot pogolemite.
|
|
|
07/11/2018 14:29:39
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
Ne razbiram kako da se znae dali vo edniot ili vo drugiot heap da se stavi? I kako treba da se implementira heap?
|
|
|
08/11/2018 22:09:23
|
petarsor
Joined: 15/07/2018 11:58:27
Messages: 87
Offline
|
VlatkoSh wrote:Ne razbiram kako da se znae dali vo edniot ili vo drugiot heap da se stavi? I kako treba da se implementira heap?
Во едниот ќе ти бидат најмалите, а во другиот најголемите. Ова може да се имплементира со множества во C++ (set, multiset), бидејќи кај нив begin() покажува на најмалиот елемент, а end() - 1 на најголемиот. Ова го има и во предавањата на МЕНДО.
http://mendo.mk/Lecture.do?id=26
На пример, замисли дека во едното множество имаме [11, 12, 13], а во другото [14, 15]. Медијаната е најголемиот елемент во првото множество.
Ако во било кој момент се извади некој елемент од првото или второто множество, можеш да преместиш елемент од едното во другото за пак да има 3 (и тоа 3-те најмали) во едното, и 2 во другото. (тука гледаме пример со 5).
Кога преместуваш, или ќе го преместуваш најголемиот елемент од првото во второто, или најмалиот елемент од второто во првото.
Во set, multiset, можеш лесно да бараш, додаваш и бришеш елементи.
|
|
|
09/11/2018 13:08:52
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
A kako da znaeme kade da go insertneme noviot element (v[i])? I dali prvo da se brise stariot (v[i-k]) element pa da se insertne noviot, ili prvo da se insertne noviot pa da se izbrise stariot?
Probuvam da ja resam ama ne mozam... bi te razbral ako go napises kodot?
|
|
|
10/11/2018 01:12:15
|
petarsor
Joined: 15/07/2018 11:58:27
Messages: 87
Offline
|
VlatkoSh wrote:A kako da znaeme kade da go insertneme noviot element (v[i])? I dali prvo da se brise stariot (v[i-k]) element pa da se insertne noviot, ili prvo da se insertne noviot pa da se izbrise stariot?
Не е тоа важно. Еве да кажеме, прво да се избрише стариот, па да се стави новиот. И дека новиот елемент секогаш ќе го ставаме во второто множество.
Но, од кога ќе ставиш нов елемент, треба да провериш неколку работи:
- дали во множествата има соодветен број на елементи (на пример, ако бараме медијана од 5 вредности, треба 3 во првото, и 2 во второто). ако има проблем, префрлувај како што опишав погоре (најголемиот од првото во второто, или најмалиот од второто во првото).
- да провериш дали најголемиот елемент од првото е помал/еднаков на најмалиот елемент од второто, бидејќи во првото треба да се помалите а во второто поголемите (ова може да не е како што треба бидејќи горе кажав дека "еве, секогаш ќе ставаме во второто"). ако е така, само направи замена (најголемиот од првото стави го во второто, и најмалиот од второто во првото). кај set/multiset ова вадење, ставање работи во logN време.
|
|
|
11/11/2018 10:42:05
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
Mislam deka implementirav se sto kaza, ama dava gresen rezultat. Veke mi se smaci od zadacava
|
|
|
11/11/2018 16:08:00
|
petarsor
Joined: 15/07/2018 11:58:27
Messages: 87
Offline
|
VlatkoSh wrote: Veke mi se smaci od zadacava
Те разбирам, ама дрвава се многу важни во натпреварите по програмирање, така да не ти е џабе изгубеното време.
Еве ти поправен код.
Обрни внимание дека немаше (sum += *s1.rbegin()) на крајот од for циклусот за да ја ажурираш сумата.
Слично, не можеш да ги сортираш првите K елементи од v на тој начин (јас направив нов вектор vcopy - види долу), бидејќи ако тие ти се сортирани, подоцна во вториот for нема да бришеш точни елементи со erase_single(s1, v[i-k]), итн.
|
|
|
|
|
|