Nəsrin Massivinin Azaldılması (Həll təhlili)

Həll

Ümumi İdeya:

Bərabər elementlərdən ibarət altdizini silmək ardıcıl eyni dəyərlərin blokunu silmək ilə bərabərdir. Buna görə, massivə seqmentlərə sıxmaq faydalı olur, hər bir seqment dəyəri və tezliyini saxlayır.

Çünki maksimum iki silmə icra edə bilərik, məqsədimiz çıxarılan elementlərin ümumi sayını maksimum etməkdir.

İki əsas mümkünlük var.

Əvvəlcə, iki ən böyük seqmenti müstəqil şəkildə sil. Seqmentlərin ölçüləri s_1 və s_2 varsa, s_1 + s_2 elementi çıxarırıq.

İkinci, qonşuları eyni dəyərə malik olan orta seqmenti sil. Orta seqment silindikdən sonra, iki qonşu hallar tək böyük seqmentə birləşir. Əgər ölçülər $x$, $y$, və $z$ varsa, çıxarıla bilən elementlərin ümumi sayı olur:

Sadəcə sıxılmış massivi skan edərək bu birləşmə vəziyyətini qiymətləndiririk və ən böyük iki seqmenti də izləyirik.

Nəhayət, maksimum çıxarılan sayı $\mathrm{cnt}$ isə, minimum qalan massiv ölçüsü isə:

Sıxışma və skan etmə addımları xətti olur. Seqmentlərin sıralağı əsas vaxt alma mərhələsidir və ən pis halda \mathcal{O}(n \log n) tələb edir, hər bir test halına ümumi mürəkkəblik \mathcal{O}(n \log n) olur.

#include <bits/stdc++.h>
using namespace std;

#define vec vector
#define all(x) x.begin(), x.end()
#define Moageza ios::sync_with_stdio(false);cin.tie(nullptr);

void solve(){
    int n;
    cin>>n;

    vec<pair<int,int>> v;
    pair<int,int> cur={0,0};

    for(int i=0;i<n;i++){
        int x;
        cin>>x;

        if(cur.first==0) cur={1,x};
        else if(cur.second==x) cur.first++;
        else{
            v.push_back(cur);
            cur={1,x};
        }
    }
    v.push_back(cur);

    int cnt=0;

    for(int i=1;i+1<v.size();i++){
        if(v[i-1].second==v[i+1].second){
            cnt=max(cnt,
                v[i-1].first+v[i].first+v[i+1].first);
        }
    }

    sort(all(v));

    if(v.size()>=2)
        cnt=max(cnt,
            v.back().first+v[v.size()-2].first);
    else
        cnt=v.back().first;

    cout<<n-cnt;
}

int main(){
    Moageza

    int t;
    cin>>t;

    while(t--){
        solve();
        cout<<'\n';
    }
}