Nasserin Paritilik Massivi Transformasiyası#12356

Nasserin Paritilik Massivi Transformasiyası (Həll təhlili)

Problem Müəllifi:	Mohammad Nasser (MOAGEZA)
Hazırlayan:	Mohammad Nasser (MOAGEZA)
Dəyiştirilmiş:	Hasan Saleh (MathModel)

Həll

Ümumi Fikir: Eyni təkklik alt massivlərində əmrlərdən istifadə edərək elementləri yalnız $1$ artırmaq olar. Əgər hər hansı bir element $a_{i} > x$ a_i > x olsa, bu mümkün deyil, çünki dəyərləri yalnız artıra bilərik.

Əsas Müşahidə:

Bir elementi artırdıqda onu qonşusu ilə cütləşdirərək ümumi əmrləri minimal edə bilərik. Strategiya elementləri kiçikdən böyüyə qədər acgöz şəkildə işləməkdir.

Algoritm:

Elementləri dəyərə görə sıralayın, ilkin mövqelərini izləyərək.
Hər bir element üçün (kiçikdən başlamaqla):
- İlk növbədə sol və sağ qonşularına baxın orijinal massivin içərisində.
- Daha kiçik dəyəri olanı seçin (birlikdə artırmaq daha ucuzdur).
- Fərqi əlavə edin: $(qon s ¸ unun dəyəri - bəzi dəyər)$ (\text{qonşunun dəyəri} - \text{bəzi dəyər}) cavaba.
- Hazırda olan elementi nəzərə almamaq.
Nəhayət, maksimum elementi $x$ etməyə $(x - max (a))$ (x - \max(a)) əlavə şəkildə əlavə edin.

Əmrlərin minimum sayı:

i = 0 \sum n - 2 (min (sol qon s ¸ u, sa g ˘ qon s ¸ u) - a_{i}) + (x - max (a))

\sum_{i=0}^{n-2} (\min(\text{sol qonşu}, \text{sağ qonşu}) - a_i) + (x - \max(a))

Həll hər bir test halı üçün $O (n lo g n)$ \mathcal{O}(n \log n) zaman müddətində işləyir sıralamaq və dəsd əməliyyatlarına görə.

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