Wątki bez odpowiedzi | Aktywne wątki
Autor |
Wiadomość |
Dołączył(a): 31 maja 2010, o 11:31 Posty: 20
|
Re: Górnicy - testy
| | | | Anisiak napisał(a): Ja zrobiłam to tak: obliczyłam bfs-em dla każdej komory jakiej maksymalnej wysokości może się do niej dostać pracownik i zapisuje, dane do tablicy; ponieważ wysokości ludzi i *komór są z przedziału od 1 do 1000 zastosowałam sortowanie kubełkowe; a potem zachłannie przydzielałam najwyższych pracowników do najwyższych komór. mam nadzieje, że trochę rozjaśniłam; *chodzi o wysokości tuneli, aby dostać się do danej komory. pozdrawiam Anisiak | | | | |
Ja robie podobnie oprocz tego BFS'a np dla. takiego testu: 1 4 4 2 1 1 3 1 2 1 4 3 3 1 1 1 Robie tak: poziom 0 - indeksy: 4 zwieksz ilosc poziomow lece po wszystkich tunelach i dodaje do ostatniego poziomu jesli a jest rowne ktoremus z indeksow na poziomie 0 to do poziomu 1 dodaje b (przy okazji maxwys dla komory[b] = min( komora[a].maxwys, aktualnytunel.maxwys); ) po czym usuwam dany tunel. Jeśli b jest rowne ktoremus z indeksow na poziomie 0 to tak samo tylko na odwrot poziom 1- indeksy : 1 zwieksz ilosc poziomow i znowu lece po tunelach... poziom 2 - indeksy: 2 oraz 3 koniec bo ilosc dodanych tuneli jest rowna n-1 To chyba daje O((E / 2) * V); co jak wiadomo jest o wiele za duzo Weż się ktoś podziel kodem to sobie przeanalizuje tego BFS'a, bo nigdy wczesniej nie robilem zadan z grafow i sam sobie nie poradze
|
31 paź 2010, o 11:25 |
|
|
Dołączył(a): 31 maja 2009, o 18:24 Posty: 107
|
Re: Górnicy - testy
|
31 paź 2010, o 11:31 |
|
|
Dołączył(a): 11 paź 2010, o 10:02 Posty: 83
|
Re: Górnicy - testy
Bez sortowania kubełkowego masz?;) a jakie masz czasy:P Test Wynik Czas Pamięć 0.out accepted 0.00s 2220 1.out accepted 0.00s 2220 2.out accepted 0.00s 2220 3.out accepted 0.00s 2220 4.out accepted 0.00s 2352 5.out accepted 0.00s 2220 6.out accepted 0.04s 3332 7.out accepted 0.13s 5572 8.out accepted 0.12s 5408 9.out accepted 0.57s 15608 10.out accepted 0.68s 20756
|
31 paź 2010, o 11:39 |
|
|
Dołączył(a): 31 maja 2009, o 18:24 Posty: 107
|
Re: Górnicy - testy
Jeśli dobrze pamiętam, to to co zastosowałem nazywa się sortowaniem przez zliczanie.
|
31 paź 2010, o 11:49 |
|
|
Dołączył(a): 27 paź 2009, o 00:30 Posty: 138
|
Re: Górnicy - testy
Zależy od źródła. "Wprowadzenie do algorytmów" wprowadza dużo zamieszania nazywając sortowaniem kubełkowym taki w zasadzie nieprzydatny algorytm. Ale poza "Wprowadzeniem" sortowanie przez zliczanie = sortowanie kubełkowe
_________________ Mięso = Morderstwo
|
31 paź 2010, o 11:52 |
|
|
Dołączył(a): 23 lis 2009, o 23:00 Posty: 101
|
Re: Górnicy - testy
| | | | Kod: //SKI 2010 //Zadanie: Górnicy //Autor: Łukasz Wałejko #include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> leafs; vector<vector<pair<int,int> > > graph; int k; void dfs(int v,int p,int h) { if(graph[v].size()==1&&v!=k) { leafs.push_back(h); } for(int i=0;i<graph[v].size();++i) { if(graph[v][i].first==p)continue; dfs(graph[v][i].first,v,min(h,graph[v][i].second)); } } int main() { int t; scanf("%d",&t); while(t--) { leafs.clear(); graph.clear(); int n; scanf("%d%d",&n,&k); int a,b,c; graph.resize(n+1); for(int i=0;i<n-1;++i) { scanf("%d%d%d",&a,&b,&c); graph[a].push_back(pair<int,int>(b,c)); graph[b].push_back(pair<int,int>(a,c)); } dfs(k,-1,1000000001); sort(leafs.begin(),leafs.end()); int m; scanf("%d",&m); vector<int> miners; miners.resize(m); for(int i=0;i<m;++i) { scanf("%d",&miners[i]); } sort(miners.begin(),miners.end()); int x=0; for(int i=0,j=0;i<leafs.size()&&j<miners.size();++i) { if(miners[j]<=leafs[i]) { ++x; ++j; } } printf("%d\n",x); } return 0; }
| | | | |
|
31 paź 2010, o 12:03 |
|
|
Dołączył(a): 31 maja 2010, o 11:31 Posty: 20
|
Re: Górnicy - testy
Wielkie dzięki. BTW jakie książki o algorytmach i strukturach danych polecacie w sensie pod konkursy ^^
|
31 paź 2010, o 14:45 |
|
|
Dołączył(a): 25 paź 2009, o 12:35 Posty: 37
|
Re: Górnicy - testy
Jak już chcesz być tró i pisać po angielsku, to liście są leaves
|
31 paź 2010, o 15:43 |
|
|
Dołączył(a): 23 lis 2009, o 23:00 Posty: 101
|
Re: Górnicy - testy
Yup, masz rację, aż sprawdziłem Aczkolwiek wymowa IMHO podobna...
|
31 paź 2010, o 19:30 |
|
|
Kto przegląda forum |
Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość |
|
Nie możesz rozpoczynać nowych wątków Nie możesz odpowiadać w wątkach Nie możesz edytować swoich postów Nie możesz usuwać swoich postów Nie możesz dodawać załączników
|
|