Riešenie hrubou silou

Úlohu vieme riešiť pomocou hrubej sily. Iterujeme zľava doprava po prvých $K$ pozíciách. Ak sa na nejakej pozícii nachádza korenička s číslom väčším než $K$, nájde sa najbližšia správna korenička s číslom $≤ K$ napravo a pomocou postupných susedných výmen sa presunie na túto pozíciu. Každá takáto výmena sa započíta do výsledku. Algoritmus pokračuje, kým prvých K pozícií neobsahuje iba koreničky 1 až K, pričom ich vnútorné poradie nie je dôležité. Týmto postupom sa nikdy nerobia zbytočné výmeny, pretože každá výmena rieši konkrétny problémový pár. Problémový pár je dvojica koreničiek, kde korenička s číslom väčším než K stojí pred koreničkou s číslom menším alebo rovným K, a každá takáto inverzia musí byť odstránená aspoň jednou susednou výmenou.

Optimálne riešenie

Kľúčové je uvedomiť si, že koreničky na indexoch $i$ a $j$ vieme vymeniť pomocou $|i - j|$ susedných výmen, takže nie je potrebné jednotlivé výmeny simulovať. Nech $p_i$ označuje index $i$-tej koreničky s číslom $\le K$ v pôvodnom poradí poľa (číslované zľava doprava). Korenička na pozícii $p_i$ má pred sebou presne $p_i - i$ koreničiek s číslom väčším než $K$, s ktorými tvorí problémové dvojice. Pole prechádzame zľava doprava. Pri každej koreničke s číslom $\le K$ pripočítame do výsledku jej aktuálny index $i$, čím získame hodnotu $$ \sum p_i. $$ Z tejto hodnoty následne odčítame $$ \sum_{i=0}^{K-1} i = \frac{(K-1)K}{2}. $$ Výsledkom je presný počet problémových dvojíc, a teda aj minimálny počet potrebných susedných výmen.

Časová a pamäťová zložitosť

Takéto riešenie bude mať časovú zložitosť $O(n)$ a pamäťovú zložitosť $O(1)$

V riešení sa využíva iba lineárne iterovanie cez prvky, pričom ich nie je potrebné ukladať do pamäte. A zopár premenných.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;
using vll = vector<long long>;
using vvll = vector<vector<long long>>;
using vstr = vector<string>;
using str = string;

#define PB push_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, s, f) for (int(i) = (s); i < (f); (i)++)
#define ROF(i, s, f) for (int(i) = (s); i > (f); (i)--)
#define loop(x) for (int i = 0; i < (x); i++)

const int INF = 1e9;
const long long LLINF = 1e18;
const int MOD = 1e9 + 7;
const long long LLMOD = 1e18 + 7;

int main(){
    ll n ,k;
    cin >>n>>k;

    vll lst(n);
    FOR(i,0,n) cin >> lst[i];
    vi pos;
    FOR(i,0,n){
        if (lst[i] <= k){
            pos.PB(i);
        }
    }
    ll ans = 0;
    FOR(i,0,k){
        ans += pos[i] - i;
    }
    cout <<ans<<'\n';
}

n,k = map(int, input().split())
pole = [int(i) for i in input().split()]
print(sum([i if pole[i] <= k else 0 for i in range(n)])-(k-1)*k//2)