军训站队

Posted on Edited on In

题目大意：小林和亮亮刚入高中，首先就迎来了军训。

用数学的语言来描述，如果把训练场看成一个平面直角坐标系，第 i 名同学所在位置的横坐标是 i，而所有同学的纵坐标本该是 0（或者任意一个相等的常量），这样就排成了一条直线。当然，由于同学们排的歪歪扭扭，所以第 i 位同学的横坐标依然是 i，而纵坐标却成了Yi （为了简化问题，我们假设所有的坐标都是整数）。对此，教官当然十分生气，因此他决定下命令调整队伍，使得所有人能够站成一条直线（也即让所有的Yi 相同）。教官的命令总共有三种：

  • 除了某一个同学外，其余所有同学向前走一步（向前走一步可理解为Yi 的 值加 1，下同）
  • 除了某一个同学外，其余所有同学向前走两步
  • 除了某一个同学外，其余所有同学向前走五步。

教官希望他能以最少的命令次数使得所有同学站成一条直线，但是他不会算，于是就让亮亮帮他来计算。亮亮虽然聪明，可是由于班上同学人数众多，他一下子也解决不了这个问题，只能来寻求会编程的你的帮助，你能告诉亮亮答案吗？

很好的一道思维题，排成一条线是一个相对的概念，因此如果一个人不动，别的同学向前走q步的话，相当于这个人向后走q步

所以对于三个指令，分别可以转化为：令Yi减1，减2，减5，所以当我们按升序给他们排序完毕之后，所有的Yi都应该减少至Y1，

Y1-1，Y1-2，Y1-3，Y1-4，这五个数之一（想一想，为什么）我们枚举所有的Yi应该减少到哪一个值，并计算出到达这一步的指令数目

求和，取min，即为答案，时间复杂度\(O(n\times logn)\)或者\(O(n)​\)（为啥？

至此问题大致已经解决，但是有个细节需要注意，为了防止减成负数，先给他加上那个贡献（见代码

代码如下：

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 66;

int n;
int a[N], b[N];

signed main()
{
    int i, j, res(0), ans;
    n = read();
    for (i = 1; i <= n; ++ i) a[i] = read();
    
    sort(a + 1, a + n + 1);
    
    for (i = n; i >= 1; -- i) a[i] -= a[1];
    for (i = 1; i <= n; ++ i) b[i] = a[i];
    
    for (j = 0; j < 5; ++ j)
    {
        ans = 0;
        for (i = 1; i <= n; ++ i) a[i] = b[i];
        for (i = 1; i <= n; ++ i) a[i] += j;//here
        for (i = 1; i <= n; ++ i)
        {
            if (a[i] >= 5) ans += a[i]/5, a[i] %= 5;
            if (a[i] >= 2) ans += a[i]/2, a[i] %= 2;
            if (a[i] > 0) ans += a[i]/1, a[i] %= 1;
        }
            
        res = ! j ? ans : min(res, ans);
    }
    put(res);
    return 0;
}