Luobuyu's Blog

0%

D.小美的数组操作

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.8k 阅读时长 ≈ 3 分钟
贪心的选择贡献的数。

D.小美的数组操作

题目描述：

小美拿到了一个数组，她每次可以进行如下操作：
选择两个元素，一个加 1，另一个减 1。

小美希望若干次操作后，众数的出现次数尽可能多。你能帮她求出最小的操作次数吗？

众数定义：在一组数据中，出现次数最多的数据，是一组数据中的原数据，而不是相应的次数。 一组数据中的众数不止一个，如数据2、3、-1、2、1、3中，2、3都出现了两次，它们都是这组数据中的众数。

数据范围：

$1\le n \le 10^5;1\le a_i \le 10^9$

题解：

首先求和 $sum$ ，如果 $sum$ 能被 $n$ 整除，则说明能搞成全一样的，计算一下加减次数就行。

如果不能整除，需要牺牲一个数字，额外的加减操作都做在该数字上，优选最大值或最小值。假设剩余的和为 $sum1$ ，求出 $sum1$ 除以 $n - 1$ 的余数，如果余数超过了 $n-1$ 的一半，说明平均值加一比较好，否则就是均值。同样统计加的次数和减的次数，求出二者的差值，差值就是需要额外做的操作的次数。

代码：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define lll long long
#define PII pair<int, int>
namespace FAST_IO
{

    inline char nextChar()
    {
        static char buf[1000000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
    }
#define getch getchar
    template <class T>
    inline void read(T &x)
    {
        T flag = 1;
        x = 0;
        char ch = getch();
        while (ch < '0' || ch > '9')
        {
            if (ch == '-')
                flag = -1;
            ch = getch();
        }
        while (ch >= '0' && ch <= '9')
        {
            x = (x << 3) + (x << 1) + (ch ^ 48), ch = getch();
        }
        x *= flag;
    }

    template <class T, class... _T>
    inline void read(T &x, _T &...y)
    {
        return read(x), read(y...);
    }

    inline void print128(lll x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            print128(x / 10);
        putchar(x % 10 + '0');
    }

} // namespace FAST_IO
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    read(n);
    ll sum = 0;
    int minx = INF, maxx = -INF, minx_index, maxx_index;
    for(int i = 0; i < n; ++i)
    {
        read(a[i]);
        sum += a[i];
        if(a[i] < minx)
        {
            minx = a[i];
            minx_index = i;
        }
        else if(a[i] > maxx)
        {
            maxx = a[i];
            maxx_index = i;
        }
    }
    ll ans = 0;
    if(sum % n == 0)
    {
        int avg = sum / n;
        ans = 0;
        for(int i = 0; i < n; ++i)
        {
            if(a[i] > avg) ans += a[i] - avg;
        }
    }
    else
    {
        // 去掉最大值，剩下的求平均值
        ans = INF_LL;
        ll tmp = 0;
        ll add_times = 0, sub_times = 0;
        int avg = (sum - maxx) / (n - 1);
        k = (sum - maxx) % (n - 1);
        if(k > n - 1 - k) avg++;
        
        for(int i = 0; i < n; ++i)
        {
            if(i == maxx_index || a[i] == avg) continue;
            if(a[i] > avg) sub_times += a[i] - avg;
            else add_times += avg - a[i];
        }
        tmp = abs(add_times - sub_times) + min(add_times, sub_times);
        ans = min(ans, tmp);
        
        avg = (sum - minx) / (n - 1);
        k = (sum - minx) % (n - 1);
        if(k > n - 1 - k) avg++;
        add_times = sub_times = 0;
        for(int i = 0; i < n; ++i)
        {
            if(i == minx_index || a[i] == avg) continue;
            if(a[i] > avg) sub_times += a[i] - avg;
            else add_times += avg - a[i];
        }
        tmp = abs(add_times - sub_times) + min(add_times, sub_times);
        ans = min(ans, tmp);
    }
    cout << ans << endl;

    return 0;
}