模拟赛题讲解[34]

来自 yukuai26 2023-08-06 noi.ac #3281

题目描述：

给你一个长度为 \(n\) 的序列，以及一个数字 \(k\)。

每次你可以选择一对 \((i,j)\)，使得 \(a_i\) 加一，\(a_j\) 减一。

问最少经过多少次操作，使得数列中任意两个数的差不超过 \(k\)。数据保证有解。

输入格式：

第一行两个整数 \(n,k\) 第二行 \(n\) 个整数，表示 \(a_i\)

输出格式：

输出最小的答案

输入样例：

4 3
1 5 1 10

输出样例：

4

数据范围：

保证 \(1 \leq n \leq 100000,1 \leq K \leq 100000,1 \leq a_i \leq 100000\)，且在该范围内等概率随机生成。

题解：

显然我们每次修改的两个数分别为最大值和最小值。

并且每次修改一定会把最小值和最大值中出现次数最少的那个给灭掉。

那么就模拟一下这个过程就好了。

时间复杂度 \(\mathcal{O}(n+\max\{a_i\})\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,k,l = INF,r,ans,a[N],b[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i], ++b[a[i]]; up(r, a[i]); down(l, a[i]);
    }
    while(r - l > k)
    {
        int x = min(b[l], b[r]); ans += x;
        b[r - 1] += x; b[r] -= x; if(!b[r]) --r;
        b[l + 1] += x; b[l] -= x; if(!b[l]) ++l;
    }
    cout << ans << '\n';
    return 0;
}