Problemformulering

Lösning

För att lösa problemet så räckte det att manuellt sortera listan och räkna hur många byten det blir - men det finns ett mer intressant sätt att se på problemet.

Låt oss först definiera ett begrepp: antalet inversioner i en permutation (i det här fallet, array) P[1...n] är antalet par av index i,j (i < j) sådana att talet vid det vänstra indexet (P[i]) är större än talet vid det högra (P[j]). Betrakta till exempel listan [3, 1, 2]. Den har två inversioner, 3-1 och 3-2.

Låt oss titta på ett extra intressant exempel - exempelindatan till problemet [14, 7, 24, 12, 15]. För enkelhets skull koordinatkomprimerar vi listan och tittar på [3,1,5,2,4] istället (detta är ekvivalent). Inversionerna i listan är: 3-1, 3-2, 5-2, 5-4, dvs exakt fyra stycken.

Svaret på problemet är alltså precis lika med antalet inversioner i listan. För att sortera listan så måste helt enkelt två element som är i fel ordning (dvs de skapar en inversion) byta plats en gång, och inte mer än en gång. Alla inversioner byter alltså plats precis en gång, och sedan är listan sorterad.

Nedan följer en koncis lösning med tidskomplexitet O(N^2) av Aron Granberg som löser problemet:

#include<iostream>
#include<vector>
 
using namespace std;
 
int main () {
    int n;
        cin >> n;
        vector<int> nums (n);
        for ( int i=0;i<n;i++) cin >> nums[i];
        
        int tot = 0;
        for ( int i=0;i<n;i++) {
                for ( int j=0;j<i;j++) {
                        tot += nums[j] > nums[i] ? 1 : 0;
                }
        }
        cout << tot << endl;
}

Med hjälp av Fenwick-träd och liknande datastrukturer kan man lösa problemet ännu mer effektivt, men eftersom listan var max 1000 lång så räcker det i det här fallet med två enkla loopar.