CF1622 C.Set or Decrease【贪心】

题目链接：codeforces 1622C

题解

贪心思想，显然，用最小的数去替换数组中的数。

答案与顺序无关，不妨先从小到大排个序，假设替换了末 个数字，当前和为 。

比较好想的是，如果当前 ，则答案就是最小的 。如果 ，则需要先减少最小的数再去替换。具体做法是：先尝试替换后 个数，求的差值 ，然后最后的次数加上 即可。因为对于一个被替换的数，先替换它再减少所需要的操作数和先减少最小的数再去替换它所需要的操作数是相等的。于是可以用总的所需要的操作数平摊到 个数。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll a[N], pre[N];
ll n, k;
int main() {
    int t; cin >> t;
    while (t--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        sort(a+1, a+1+n);
        for (int i = 1; i<= n; i++) {
            pre[i] = pre[i-1] + a[i];
        }
        ll ans = 2e15;
        for (int j = 0; j < n; j++) {
            ll sum = pre[n-j] + a[1] * j;
            ll tmp = j;                  
            if (k < sum) { 
                ll dif = sum - k;
                tmp += (dif+j) / (j+1);
            }
            ans = min(ans, tmp);
        }
        cout << ans << endl;
    }
    return 0;
}