[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Meteo ured  XML
Forum Index » Други задачи
Author Message
VlatkoSh


[Avatar]

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?
Бале



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


[Avatar]

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?
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, можеш лесно да бараш, додаваш и бришеш елементи.
VlatkoSh


[Avatar]

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?
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 време.
VlatkoSh


[Avatar]

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

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]), итн.


 
Forum Index » Други задачи
Go to:   
Powered by JForum 2.1.8 © JForum Team