Wieksze mniejsze - zadanie

[RediioS]

Pomoże ktoś w rozwiązaniu tego zadania:

 

Pani wypisała na tablicy pewną ilość liczb, a następnie każdemu uczniowi z klasy przydzieliła pewną dodatnią liczbę całkowitą C. Każdy z uczniów musi policzyć ile liczb z tablicy jest większych od C, a ile mniejszych od C. Niektórzy z uczniów poprosili Cię o pomoc.

 

 

Wejście

W pierwszym wierszu liczba N - ilość liczb wypisanych na tablicy (1<=N<=20000), w drugim wierszu N liczb oddzielonych pojedynczą spacją (kolejne liczby wypisane na tablicy, których wartość bezwzględna nie przekracza 20000), w następnym, trzecim wierszu liczba U - ilość uczniów w klasie (1<=U<=20000), w następnych U wierszach przydzielane liczby C dla kolejnych uczniów (z zakresu 1<=C<=200) .

 

Wyjście

Dla każdego ucznia w kolejnych U wierszach 2 liczby a i b oddzielone pojedynczą spacją, gdzie a - ilość liczb większych od C, b - ilość liczb mniejszych od C.

 

Przykład

Dla danych wejściowych:

5

2 3 4 5 6

4

1

3

5

7

poprawnym wynikiem jest:

5 0

3 1

1 3

0 5

 

 

 

Udało mi się zrobić coś takiego lecz działa za wolno jakby ktoś mogł przerobić ten kod, aby działał szybciej:

 

 

 

#include <iostream>
#include <cstdio>
using namespace std;



int n, w, m, u, C;
int main()
{
scanf("%d",&n);
int t[n];

for(int i=0; i<n; i++)
{
scanf("%d",&t[i]);
}

scanf("%d",&u);


for(int j=0; j<u; j++)
{
scanf("%d",&C);
w=0;
m=0;
for(int g=0; g<n; g++)
{




if(C<t[g])w++;
if(C>t[g])m++;
}
printf("%d",w);
printf(" ");
printf("%d\n",m);
}


cin.ignore(2);
return 0;
}
 

 

[Squezee]

Spróbuj tak:

#include <iostream>
using namespace std;

int main()
{
    int ilosc_liczb, ilosc_uczniow;
    cin >> ilosc_liczb;
    int *tablica = new int[ilosc_liczb];
    for(int i = 0; i < ilosc_liczb; i++)
        cin >> tablica[i];
    cin >> ilosc_uczniow;
    int *liczby_uczniow = new int[ilosc_uczniow];
    for(int i = 0; i < ilosc_uczniow; i++)
        cin >> liczby_uczniow[i];

    int wieksze, mniejsze;
    for(int i = 0; i < ilosc_uczniow; i++)
    {
        wieksze = 0, mniejsze = 0;
        for(int j = 0; j < ilosc_liczb; j++)
        {
            if(liczby_uczniow[i] > tablica[j]) mniejsze++;
            if(liczby_uczniow[i] < tablica[j]) wieksze++;
        }
        cout << wieksze << " " << mniejsze << "\n";
    }
  delete [] tablica;
  delete [] liczby_uczniow;
  return 0;
}

[Krycho]

To jest podejscie naiwne o czasie O(n^2) wiec tym samym co jego algorytm. Da sie to sporo przyspieszyc.

[Lesteross]

Możecie powiedzieć, skąd macie te zadania? Bo kiedyś pamiętałem ale teraz już nie wiem .

[RediioS]

Ja to mam z warsztatów informatycznych, ale pewnie jest takie zadanie gdzies w internecie

[Krycho]

http://ideone.com/khnWG9

 

Zamiast pisac rozwiazania silowe lepiej sie czasami zastanowic i napisac cos optymalniejszego, a nie pierwsze co nam przyjdzie do glowy.

[Sopelek997]

dodatkowo użyłbym informacji czy szukana liczba jest mniejsza czy większa od ostatniej znalezionej. (wytłumaczę bardziej. Student x ma przydzieloną wartość y. Po znalezieniu wartości y zapisujemy ją. Jeśli wartość przydzielona następnemu studentowi jest większa od y to szukamy po prawej stronie od wartości y, a jeśli mniejsza to po lewej.)

 

Powinno dać to nieco lepsze wyniki.

[HellMT2]

nie mam pojęcia

[Krycho]

dodatkowo użyłbym informacji czy szukana liczba jest mniejsza czy większa od ostatniej znalezionej. (wytłumaczę bardziej. Student x ma przydzieloną wartość y. Po znalezieniu wartości y zapisujemy ją. Jeśli wartość przydzielona następnemu studentowi jest większa od y to szukamy po prawej stronie od wartości y, a jeśli mniejsza to po lewej.)

 

Powinno dać to nieco lepsze wyniki.

 

Nie ma co przesadzac z optymalizacja. To i tak wykona sie na tyle szybko, ze nie ma sensu kombinowac, zeby zbic czas o 0.01s. Kod jest teraz na tyle prosty i czytelny, ze nie co go optymalizowac. Nadal zlozonosc pozostanie O(n*log_2(n)) bo najwolniejsze bedzie sortowanie, reszta wykonuje sie liniowo.