Nie bardzo rozumiem o co chodzi w zadaniu 'Rotacje na drzewie' z zeszłorocznej OI: [url]http://main.edu.pl/pl/archive/oi/18/rot[/url]
Próbowałem liczyć na różne sposoby i zawsze wychodzi inny wynik niż powinien. Czym w końcu są te inwersję? Z treści wynika, że jedna inwersja to para pozycji w koronie, na których liczba z lewej jest większa od tej z prawej. Ułożyłem do tego algorytm i wychodzą liczby parę razy większe niż w odp. Nawet ręcznie licząc można do tego dojść. Co źle rozumiem?
- Rejestracja:ponad 14 lat
- Ostatnio:ponad 9 lat
0
C++ - Rejestracja:prawie 17 lat
- Ostatnio:prawie 13 lat
0
W zadaniu chodzi o utworzenie możliwie najlepszego drzewa za pomocą zadaniowych rotacji i określenie liczby inwersji.
W przykładzie mamy np. ((3, 1), 2), które ma dwie inwersje: 3>1, 3>2. Najlepsze drzewo (być może jedno z najlepszych) to drzewo ((1, 3), 2), które zawiera już tylko jedną inwersję, tj. 3>2.
- Rejestracja:ponad 14 lat
- Ostatnio:ponad 9 lat
0
Oto co udało mi się zrobić. Miałem nadzieję, że zadziała, ale niestety :/
#include <stdio.h>
unsigned n, p, inversions;
unsigned values[200000], ptr;
// Struktura drzewa //
struct STree {
unsigned value, count, sum;
STree *left;
STree *right;
STree() : value(0), count(0), sum(0), left(NULL), right(NULL) {}
} *root; // pierwszy element (korzeń
// DEKLARACJE FUNKCJI //
bool IsBigger(STree *whare, unsigned what);
void SwapPlaces(STree *what);
void FillTable(STree *point);
// Funkcja pobierająca dane do drzewa //
unsigned FillTree(STree *current) {
scanf("%d", &p);
if(p == 0) {
current->left = new STree;
current->right = new STree;
current->sum = FillTree(current->left) + FillTree(current->right);
current->count = current->left->count + current->right->count;
if(current->left->sum / current->left->count > current->right->sum / current->right->count)
SwapPlaces(current);
return current->sum;
} else {
current->value = p;
current->sum = p;
current->count = 1;
return p;
}
}
// Funkcja zliczająca inwersje //
void Inversions() {
FillTable(root);
for(unsigned i = 0; i < n; i++) {
for(unsigned j = i; j < n; j++) {
if(values[i] > values[j]) inversions++;
}
}
}
// MAIN //
int main() {
root = new STree;
scanf("%d", &n);
FillTree(root);
Inversions();
printf("%d", inversions);
return 0;
}
// Funkcja sprawdzająca czy w danym węźle znjaduje się liczba większa od podanej //
bool IsBigger(STree *where, unsigned what) {
if(where->left->value == 0) {
if(IsBigger(where->left, what)) return true;
} else if(where->left->value > what) return true;
if(where->right->value == 0) {
if(IsBigger(where->right, what)) return true;
} else if(where->right->value > what) return true;
return false;
}
// Funkcja zamieniająca miejscami dzieci węzłą //
void SwapPlaces(STree *what) {
STree *Tmp = what->left;
what->left = what->right;
what->right = Tmp;
}
// Funkcja spisująca koronę drzewa do tablicy - od lewej //
void FillTable(STree *point) {
if(point->left->value == 0)
FillTable(point->left);
else {
values[ptr] = point->left->value;
ptr++;
}
if(point->right->value == 0)
FillTable(point->right);
else {
values[ptr] = point->right->value;
ptr++;
}
}
Nie potrafię wymyślić dobrego algorytmu. Ten w kodzie polega na rotacjach liczby(po kolei od 1 do n) tak, żeby znajdowała się ona przed większymi od niej. Niestety tak nie rozwiązuje nawet przykładowego zadania.
EDIT: Pomyliłem się, zadanie z przykładu oraz 6 innych z testów rozwiązuje. Teraz będę debugować na podstawie drugiego testu, może gdzieś wkradł się drobny błąd. Ale i tak przy połowie wywłaszcza :/
EDIT 2:
Zaktualizował kod i teraz przechodzi 14 testów, ale nie mam pojęcia jaki powinien być prawidłowy algorytm
edytowany 8x, ostatnio: mark075