Перетворення масиву за парністю від Насера#12356

Перетворення масиву за парністю від Насера (Розбір)

Автор задачі:	Мохаммад Насер (MOAGEZA)
Підготовлено:	Мохаммад Насер (MOAGEZA)
Редактор:	Хасан Салех (MathModel)

Рішення

Загальна ідея: Ми можемо лише збільшувати елементи на $1$ , використовуючи операції на підмасивах з однаковою парністю. Якщо будь-який елемент $a_{i} > x$ a_i > x, це неможливо, оскільки ми можемо лише збільшувати значення.

Ключове спостереження:

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

Алгоритм:

Відсортувати елементи за значенням, відслідковуючи їхні початкові позиції.
Для кожного елемента (починаючи з найменшого):
- Подивитися на його лівого та правого сусіда в початковому масиві.
- Вибрати сусіда з меншим значенням (коштує менше збільшити разом).
- Додати різницю: $(значення сусіда - поточне значення)$ (\text{значення сусіда} - \text{поточне значення}) до відповіді.
- Видалити поточний елемент із розгляду.
Врешті-решт, додати $(x - max (a))$ (x - \max(a)) для доведення максимального елемента до $x$ .

Мінімальна кількість операцій дорівнює:

i = 0 \sum n - 2 (min (лівий сусід, правий сусід) - a_{i}) + (x - max (a))

\sum_{i=0}^{n-2} (\min(\text{лівий сусід}, \text{правий сусід}) - a_i) + (x - \max(a))

Рішення працює за час $O (n lo g n)$ \mathcal{O}(n \log n) на тестовий випадок завдяки сортуванню та операціям із множинами.

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

void solve(){
    int n, x, mx = 0, ans = 0;
    cin >> n >> x;
    vector<int> a(n);
    set<int> s;
    vector<pair<int, int>> v;
    
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
        s.insert(i);
        v.push_back({a[i], i});
    }
    
    if(mx > x){
        cout << -1;
        return;
    }
    
    sort(v.begin(), v.end());
    
    for(int i = 0; i < n - 1; i++){
        int val = v[i].first, idx = v[i].second;
        int res1 = 2e9, res2 = 2e9;
        s.erase(idx);
        
        auto it = s.upper_bound(idx);
        if(it != s.end()){
            res1 = a[*it];
        }
        if(it != s.begin()){
            it--;
            res2 = a[*it];
        }
        
        ans += min(res1, res2) - val;
    }
    
    ans += x - mx;
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while(t--){
        solve();
        cout << '\n';
    }
    return 0;
}