针对CSP-J/S的每日一练：Day 8

一、审题

题目描述

小明正在玩一个游戏。游戏中有一个长度为 $n$ 的序列，每个位置上有一个数字。现在，小明可以进行若干次操作，每次操作可以选择一个位置上的数字 $x$，并将其加上 $1$ 或减去 $1$，即将它变成 $x+1$ 或 $x-1$。小明希望进行若干次操作之后，序列中所有数字都相等，你可以输出小明需要进行的最少操作次数。

输入格式

输入的第一行包含一个整数 $n$，表示序列的长度。
接下来一行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$，表示序列中每个位置上的数字。

输出格式

输出一个整数，表示小明需要进行的最少操作次数。

数据范围

$1\le n\le 100$
$1\le a_i\le 100$

样例1

输入

4
1 2 3 4

输出

4

样例2

输入

3
1 100 1

输出

98

来源

2019 CSP-J 第1题

二、思路

若干次操作后要使所有数字相等，显然需要将所有数变成它们的平均数。

如果平均数不是整数，需要先将所有数变化到最接近平均数的整数，然后再把它们变成平均数。变化到最接近平均数的整数不会超过0.5次操作。

如果平均数是整数，则只需要将每个数变化到平均数即可。

三、代码实现

#include 
using namespace std;
const int N = 110;
int n;
int a[N];

int main()
{
   cin >> n;

   int sum = 0;
   for (int i = 0; i < n; i++)
   {
       cin >> a[i];
       sum += a[i];
   }
   int avg = sum / n;

   int res = 0;
   for (int i = 0; i < n; i++)
   {
       res += abs(a[i] - avg);
   }

   if (sum % n != 0)
   {
       int cnt1 = 0, cnt2 = 0;
       for (int i = 0; i < n; i++)
       {
           if (a[i] < avg)
           {
               cnt1 += avg - a[i];
           }
           else if (a[i] > avg + 1)
           {
               cnt2 += a[i] - avg - 1;
           }
       }
       res += min(cnt1, cnt2);
   }

   cout << res / 2 << endl;
   return 0;
}
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