Witam,
W jaki sposób można zoptymalizować ten kod? Tak żeby nie działał w czasie kwadratowym?
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> kand(n);
for (int i = 0; i < n; i++)
cin >> kand[i];
vector<int> sorted = kand;
sort (sorted.begin(), sorted.end(), greater<int>());
vector <int> sorted_ocena(n);
for (int i = 0; i < n; i++)
{
sorted_ocena[i] = i + 1;
if(n != 0)
if (sorted[i] == sorted[i-1])
sorted_ocena[i] = sorted_ocena[i-1];
}
vector<int> ocena(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (kand[i] == sorted[j])
ocena[i] = sorted_ocena[j];
for (int i = 0; i < n; i++)
cout << ocena[i] << " ";
return 0;
}
Treść zadania dla wyjaśnienia:
Konkurs programistyczny zgromadził dużą liczbę uczestników, którzy zdobywali punkty w różnych
konkurencjach. Każdy uczestnik zapisując się do konkursu otrzymywał kolejny numer startowy. Na
koniec zawodów, powstała lista wyników.
Napisz program, który na podstawie wyników układa ranking uczestników. Jeśli wystartowało 5
zawodników uzyskując wyniki:
11 15 25 15 31
Ich rankingi są następujące:
5 3 2 3 1
Zwróć uwagę na remisy. Jeśli takowy wystąpił, ranking wszystkich miejsc dzielonych jest taki sam.
Można powiedzieć, że ranking uczestnika to liczba o jeden większa niż liczba uczestników, którzy
osiągnęli lepszy od niego wynik punktowy.