algorithm - 无法理解算法

Question

这是问题的链接
https://www.hackerrank.com/challenges/equal

我读了它的社论，无法理解。如果您没有在hackerrank上注册任何帐户，那么您肯定不会看到它的社论，所以这里有一些社论。

This is equivalent to saying, christy can take away the chocolates of one coworker by 1, 2 or 5 while keeping others' chocolate untouched.
Let's consider decreasing a coworker's chocolate as an operation. To minimize the number of operations, we should try to make the number of chocolates of every coworker equal to the minimum one in the group(min). We have to decrease the number of chocolates the ith person A[i] by (A[i] - min). Let this value be x.

This can be done in k operations.

k = x/5 +(x%5)/2 + (x%5)%2 

从这里我无法理解

Let f(min) be sum of operations performed over all coworkers to reduce each of their chocolates to min. However, sometimes f(min) might not always give the correct answer. It can also be a case when

f(min) > f(min-1)

f(min) < f(min-5)

as f(min-5) takes N operations more than f(min) where N is the number of coworkers. Therefore, if

A = {min,min-1,min-2,min-3,min-4}
then f(A) <= f(min) < f(min-5)

有人可以帮助我理解为什么需要检查 f(min),f(min-1),...,f(min-4)

Answer 1

考虑案例 A = [1,5,5]
正如社论所说，直觉上认为改变是最优的A到 [1,1,1] 用 4(2 减 2)次运算，但最好用 3 次(1 减 1, 2 减 5)次运算将其改为 [0,0,0]。

因此如果 min = minimum element in array ，然后将所有元素更改为 min可能不是最优的。

你不明白的部分是为了迎合这种情况，我们知道min可能不是最佳的 min-x也许更好，但有多大 x ?嗯，是 4 .社论说如果我们知道x最多为 4，我们可以简单地暴力破解 min , min-1 ... min-4不用想太多，看看哪个是最小的。

x <= 4 的推理(不是证明!)

如果 x >= 5，那么您必须至少对所有元素使用额外的 N 类型 3(减 5)操作，这绝对不值得。

基本上不是操作类型的问题，是因为你需要使用对所有元素进行相同的操作 ，这样做之后，问题并没有减少，元素之间的相对差异仍然相同，而您的目标是将相对差异设为0，您花费了电话 一无所获。

换句话说，如果 x >= 5，那么 x-5 一定是一个更优的目标选择，实际上 x%5 一定是最好的目标。

(以下是 TL;DR 部分:第 2 版)如果您对证明不感兴趣，请跳到最后一部分

在写原方案的过程中，我怀疑 x <= 2 事实上，我已经尝试在 HackerRank 上提交一个代码，它只检查 f(min-x) where x <= 2 的最小值。 ，并获得了 ACed。

更正式地说，我声称

If 5> (z-min)%5 >= 3 and (z-min')%5==0, then F(min')< F(min) where min'=min-x for x<=2, F(k) = min # of operation for element z to become k

(注意符号，我使用 F() ，它与问题中的 f() 含义不同)

这是证据:

如 (z-min)%5 = 1 or 2 ，那么它至少需要 (z-min)/5 + 1操作，而 (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1操作，意味着 F(min') = F(min)
如 (z-min)%5 == 3 or 4 ，那么它至少需要 (z-min)/5 + 2操作，而 (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1操作，意味着 F(min') < F(min) (or F(min') = F(min)+1)
所以我们证明

If 5> (z-min)%5 >= 3 and (z-min')%5==0, then F(min')< F(min) where min'=min-x

现在让我们证明 x的范围

正如我们假设的 (z-min)%5 >= 3 and (z-min')%5 == 0 ,

所以 (z-min')%5 = (z-min+x)%5 = ((z-min)%5 + x%5)%5 == 0
现在，如果 x >= 3 ，然后 (z-min)%5永远不能 >= 3 才能使 ((z-min)%5 + x%5)%5 == 0
如果 x = 2，则 (z-min)%5 可以是 3；如果 x = 1 那么 (z-min)%5 可以是 4，以满足两个条件: 5> (z-min)%5 >= 3 and (z-min')%5==0
因此我们一起展示

If 5> (z-min)%5 >= 3 and (z-min')%5==0, then F(min')< F(min) where min'=min-x for x<=2

请注意，始终可以生成数组 P，例如 f(min') < f(min)，因为您始终可以重复整数，这些整数可以通过这种方法进行改进，直到它超出那些整数不能的数量为止。这是因为对于无法改进的元素，它们总是需要再进行 1 次操作

例如:让 P = [2,2,2,10] f(min) = 0+3 = 3, f(min-2) = 3+2 = 5

这里 10 是可以改进的元素，而 2 不能，所以我们可以在数组中添加更多的 10。每 2 将使用 1 个更多的操作来获得 min' = min-2 , 而每 10 将节省 1 个操作以获得 min' .所以我们只需要添加更多的 10，直到它消除(补偿)2 的“浪费”:

P = [2,2,2,10,10,10,10,10]，那么 f(min) = 0+15 = 15, f(min-2) = 3+10=13

或者干脆只是

P = [2,10,10], f(min) = 6, f(min-2) = 5

(TL 结束；DR 部分!)

已编辑

OMG HACKERRANK 的测试用例很弱!

故事是当我今天早上到达我的办公室时，我一直在思考这个问题，并认为我的代码中可能存在问题(得到了 AC!)

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int T, n, a[10005], m = 1<<28;

int f(int m){
    m = max(0, m);
    int cnt = 0;
    for(int i=0; i<n;i++){
        cnt += (a[i]-m)/5 + (a[i]-m)%5/2 + (a[i]-m)%5%2;
    }
    return cnt;
}

int main() {
    cin >> T;
    while(T--){
        m = 1<<28;
        cin >> n;
        for(int i=0; i<n;i++) cin >> a[i], m = min(m,a[i]);

        cout <<  min(min(f(m), f(m-1)),f(m-2)) << endl;
    }
    return 0;
}

你能看出问题吗？

问题是 m = max(0, m); !

它确保 min-x必须至少为 0，但是等等，我上面的证明没有说明 min-x 的范围。 !它确实可以是负面的!

记住最初的问题是关于“添加”，所以目标没有最大值；当我们将问题建模为“减去”时，目标也没有最小值(但我将其设置为 0!)

用上面的代码试试这个测试用例:

1
3
0 3 3

它强制 min-x = 0，所以它给出 4 作为输出，但答案应该是 3

(如果我们使用“加法”模型，目标应该是 10，a[0],a[2] +5，a[0],a[1] +5，a[1] +2， a2])

所以当我删除 m = max(0, m); 行时，一切终于正确(我认为......) ，它允许 min-x得到否定并给出 3 作为正确的输出，当然新代码也得到 ACed ......