Зменшення Масиву Нассером (Розбір)

Розв'язок

Загальна ідея:

Зауважте, що видалення підмасиву однакових елементів еквівалентно видаленню цілого блоку підряд однакових значень. Тому доцільно стиснути масив у сегменти, де кожен сегмент зберігає значення та його частоту.

Оскільки ми можемо виконати щонайбільше два видалення, наша мета стає максимізувати загальну кількість видалених елементів.

Є два основні можливості.

По-перше, незалежно видалити два найбільших сегменти. Якщо розміри сегментів дорівнюють s_1 та s_2, ми видаляємо s_1 + s_2 елементів.

По-друге, видалити середній сегмент, сусіди якого мають однакове значення. Після видалення середнього сегменту два сусідніх випадки зливаються в один більший сегмент. Якщо їхні розміри дорівнюють $x$, $y$, та $z$, загальна кількість видалених елементів стає:

Ми просто скануємо стиснений масив, щоб оцінити цей сценарій злиття та також відслідковувати два найбільших сегменти.

Нарешті, якщо максимальна кількість видалених елементів дорівнює $\mathrm{cnt}$, мінімальний розмір залишкового масиву буде:

Компресія та сканування кроки є лінійними. Сортування сегментів домінує час виконання й вимагає \mathcal{O}(n \log n) у найгіршому випадку, надаючи загальну складність \mathcal{O}(n \log n) на тестовий випадок.

#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';
    }
}