1622C - Set or Decrease

Give an integer array $a_1, a_2, ..., a_n$ and an integer $k$. If you can either make $a_i = a_i - 1$ or $a_i = a_j$, what is the minimum number of steps you need to make the sum of array $\sum_{i=1}^n a_i <= k$?

Let's do it in a greedy way. Sort the array in an non-deceasing order. Apply operation one on $a_1$ $x$ times and apply operation two from $a_n$ $y$ times. The final array would look like $(a_1 - x), a_2, a_3, ..., a_{n - y}, (a_1 - x), (a_1 - x), ..., (a_1 - x)$. So we need to minimize the value of $x + y$ and we need $(a_1 - x) * (y + 1) + pref(n - y) - a_1 <= k$ where $pref$ is the prefix sum which can be precomputed beforehand. Rearrange it to get the minimum possible $x$ by iterating $y$ ,

$$x = a_1 - \lfloor \frac{k - pref(n - y) + a_1}{y + 1} \rfloor$$

Solution:

long long safe_floor(long long x, long long y) {
    long long res = x / y;
    while (res * y > x) res--;
    return res;
}

void solve() {
    long long n, k; cin >> n >> k;
    vector<long long> a(n);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    vector<long long> pref(n + 1);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + a[i];
    }
    long long ans = 9e18;
    for (int y = 0; y < n; y++) {
        long long x  = a[0] - safe_floor(k - pref[n - y] + a[0], y + 1);
        x = max(0LL, x);
        ans = min(ans, x + y);
    }
    cout << ans << endl;
}