Zadanie, polega na symulacji kolejki priorytetowej przy pomocy kopca. Na wejściu program dostaję liczbę operacji, później kolejne litery oznaczają odpowiednie operacje np A 23 10 (dodanie osoby o id=23 deklarującej napiwek 10), I 23 11 (osoba o id=23 zwiększa swój napiwek o 11). Operacja P wypisuje id pierwszej osoby w kolejce. Pierwsza jest ta z największym napiwkiem, lub gdy kilka osób ma taki sam napiwek to pierwsza jest ta z najmniejszym id. Mój kod jest taki:
#include <stdio.h>
int i, dl = 0;//dl(aktualna ilosc elementow w kopcu), i(indeks aktualnego elementu w kopcu)
struct algolczyk{
int id, napiwek;
};
void przesiej_w_gore(struct algolczyk *tab, struct algolczyk temp){//ustawia syna na miejscu ojca
tab[i] = tab[i/2];
tab[i/2] = temp;
i /= 2;
}
void przesiej_w_dol(struct algolczyk *tab, int a){//ustawia ojca na miejscu syna
tab[i] = tab[2*i+a];
tab[2*i+a] = tab[dl+1];
i = i*2+a;
}
int main(){
char operacja;
int j, n;
struct algolczyk tab[100002], temp;
scanf("%d", &n);//wczytywanie ilosci operacji
for(j=0; j<n; j++){
scanf("%s", &operacja);//wczytywanie typu pojedynczej operacji A, I, P
switch (operacja){
case 'A'://DODAWANIE ALGOLCZYKA DO KOLEJKI (poczatek)
scanf("%d %d", &temp.id, &temp.napiwek);
dl++;
tab[dl] = temp;
for(i=dl; i>1 && ( (tab[i].napiwek > tab[i/2].napiwek) || (tab[i].napiwek == tab[i/2].napiwek) && (tab[i].id < tab[i/2].id) );)
przesiej_w_gore(tab, temp);
break;//DODAWANIE ALGOLCZYKA DO KOLEJKI (koniec)
//------------------
case 'I'://ZWIEKSZANIE NAPIWKU (poczatek)
scanf("%d %d", &temp.id, &temp.napiwek);
for(i=1; (i<=dl) && (tab[i].id != temp.id); i++);//odszukanie odpowieniego algolczyka w kopcu
tab[i].napiwek += temp.napiwek;
while(i > 1 && ( (tab[i].napiwek > tab[i/2].napiwek) || (tab[i].napiwek == tab[i/2].napiwek) && (tab[i].id < tab[i/2].id) ) )
przesiej_w_gore(tab, temp);
break;//ZWIEKSZANIE NAPIWKU (koniec)
//------------------
case 'P'://OBSLUGIWANIE ALGOLCZYKA (poczatek)
if(dl == 0)
printf("BRAK\n");
else{
printf("%d\n", tab[1].id);
tab[1] = tab[dl];
dl--;
for(i=1; 2*i<=dl;){
if((2*i+1>dl && 2*i<=dl) && (tab[i].napiwek<tab[2*i].napiwek || tab[i].napiwek == tab[2*i].napiwek && tab[i].id > tab[2*i].id))
przesiej_w_dol(tab, 0);
else if((2*i+1<=dl) && (tab[i].napiwek<=tab[2*i].napiwek || tab[i].napiwek<=tab[2*i+1].napiwek)){
if((tab[2*i].napiwek > tab[2*i+1].napiwek) || (tab[2*i].napiwek == tab[2*i+1].napiwek && tab[2*i].id < tab[2*i+1].id))
przesiej_w_dol(tab, 0);
else if((tab[2*i].napiwek < tab[2*i+1].napiwek) || (tab[2*i].napiwek == tab[2*i+1].napiwek && tab[2*i].id > tab[2*i+1].id))
przesiej_w_dol(tab, 1);
}
else
break;
}//---
}
break;//OBSLUGIWANIE ALGOLCZYKA (koniec)
}
}
return 0;
}
Pierwsze pytanie jest takie, czy jest ktoś w stanie znaleźć tutaj błąd? Już siedzę nad tym po kilka godzin dziennie od ponad tygodnia, a błędu nie widzę. Może przekracza jakiś rozmiar, bo operacji może być max 10 000, gdzie wartość napiwku dodawanego może być też max 10 000, czyli w skrajnym przypadku napiwek może wynosić 100 000 000. nr ID nie może być większy niż 150 000. Testowałem, już na różnych danych program i zawsze wyświetla wg mnie poprawne wyniki. Wydaje mi się, że jeśli jest błąd to gdzieś w tym kawałku case: 'P'. Chociaż pisałem już ten fragment chyba na 4 różne sposoby
A drugie pytanie to czy program trzyma się złożoności O(n * log(n))? Obawiam się że w case: 'I' psuje go linia odszukująca odpowiedniego id w kopcu.