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: ```cpp 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; } ```