Nasser's Array Equalizer (Editorial)

Solution

General Idea: We need to make all elements equal with minimum total cost, where the cost of an operation is the maximum element in the chosen subarray.

First, if all elements are already equal, the answer is $0$.

Otherwise, we have two main strategies:

Strategy 1: Set everything to the maximum element.

• Cost: One operation covering the entire array.

• Total cost = maximum element in the array.

Strategy 2: Keep the maximum element unchanged and change everything else.

• Split the array into segments separated by the maximum element.

• For each segment, the cost is the maximum element in that segment.

• Total cost = sum of maximum elements in all segments.

The answer is the minimum of these two strategies.

Why Strategy 2 works:

When we keep the maximum element and change segments between occurrences of the maximum:

Since each segment doesn't contain the global maximum, this can be cheaper than using the global maximum once.

The solution runs in $\mathcal{O}(n)$ time per test case.

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

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    int mx=0,mn=1e9;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        mx = max(mx, v[i]);
        mn = min(mn, v[i]);
    }
    
    if (mx == mn) {
        cout << 0;
        return;
    }
    
    int ans1 = mx;  // Strategy 1: change everything
    int ans2 = 0, temp = 0;
    
    // Strategy 2: keep maximum, change segments
    for (int i = 0; i < n; i++) {
        if (v[i] == mx) {
            ans2 += temp;
            temp = 0;
        } else {
            temp = max(temp, v[i]);
        }
    }
    ans2 += temp;
    
    cout << min(ans1, ans2);
}

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