Zadanie Sortowanie

Question

Mam problem z takim zadaniem: https://sio2.mimuw.edu.pl/c/oij15-wiekuisty-oboz/p/sor/

Ma ktoś jakiś pomysł? Srednio mi idzie.

Answer 1

Mam pomysł, ale trzeba go przetestować. To że możemy zamieniać za darmo elementy oddalone o 2 oznacza, że mozemy dowolnie permutować wszystkie pozycje parzyste ze sobą i wszystkie nieparzyste ze sobą za darmo. To w takim razie dla każdego elementu tablicy sprawdźmy na jakiej pozycji będzie po posortowaniu (parzystej pozycji czy nieparzystej) i minimalny kosz posortowania to koszt poprzesuwania elementów tablicy tak żeby były na pozycjach o tej samej parzystości co w posortowanej tablicy.

Comments

Super rozwiązanie, przeszło na 100. Bez usprawnienia wchodzi na 60pkt (wszystkie liczby sa parami rozne) tak naiwnie poprostu sort i petla for liczenie, na 100 trzeba bylo trochę podrasować, zrobic mapa, ile jest parzystych, ile nieparzystych i jak posortujemy te liczby tak jak maja byc na wyjsciu, to sprawdzac ile zostało nam jeszcze parzystych, a ile nieparzystych i jak np. i jest parzyste, a licznik parzystych tego elementu to 0, to wyn++. O(n log n), ze względu na posortowanie danych i mapa. To zadanie było z obozu przygotowywującego do EJOI-a, a wsumie to juz 3 zadanie jakie robię z tego obozu i wszystkie wydawały się trudne, a rozwiązanie okazuje się proste. Kod:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int n = 0, wczytana_liczba = 0, ile_zmian = 0;
vector<int> elementy;
unordered_map<int,pair<int,int>> stat; // Wartosc, ile parzystych, ile nieparzystych.

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        elementy.push_back(wczytana_liczba);
        if (auto it = stat.find(wczytana_liczba) == stat.end())
            stat.insert({wczytana_liczba,{0,0}});
        if (i % 2 == 0)
            stat[wczytana_liczba].first++;
        else
            stat[wczytana_liczba].second++;
    }
    sort(elementy.begin(),elementy.end());
    for (int i = 0; i < n; ++i)
    {
        if (i % 2 == 0)
        {
            if (stat[elementy[i]].first > 0)
                stat[elementy[i]].first--;
            else
                ile_zmian++;
        }
        else
        {
            if (stat[elementy[i]].second > 0)
                stat[elementy[i]].second--;
            else
                ile_zmian++;
        }
    }
    printf("%d",ile_zmian / 2);
    return 0;
}

Jeszcze raz dziękuję!!!!!

edit: Warto podkreślić, że idx-ow do zamiany(wyn) będzie zawsze parzyście wiele, nie zdarzy się tak, że będzie ich nieparzyście, bo jeśli liczba x jest na zlym idx-ie, to generuje liczbe x', ktora tez jest na zlym idx-ie.