无法理解算法

Question

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

我读了它的社论，却听不懂。如果你没有考虑到hackerrank，那么你肯定不会看到它的社论，下面是一些社论。

这相当于说，克丽丝蒂可以拿走一位同事的巧克力1，2或5，同时保持其他人的巧克力不动。 让我们考虑减少同事的巧克力作为一种手术。为了减少手术的数量，我们应该努力使每个同事的巧克力数量与小组中的最小巧克力数量相等。我们必须减少第一个人艾尔的巧克力数量(艾民).让这个值是x。

This can be done in k operations.

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

，从这里我无法理解

让f( min )是对所有同事进行的操作的总和，以便将他们的巧克力减少到最小。然而，有时f(min)可能并不总是给出正确的答案。这也可能是当

f(min) > f(min-1)

f(min) < f(min-5)

当f(min-5)比f(min)更多时，N是同事的数目。因此，如果

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和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，您将N操作的代价为零。

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

(下面是TL;DR part: Version 2)如果你对证据不感兴趣，跳到最后一节

在编写原始解决方案的过程中，我怀疑x <= 2确实存在，我尝试在HackerRank上提交一个只检查f(min-x) where x <= 2最小值的代码，得到了ACed。

更正式一点，我声称

如果5> (z- min )%5 >= 3和(z-min')%5==0，则F(min')< F(min)其中min'=min-x表示x<=2，F(k) =z操作的min#使z成为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)

所以我们证明

如果5> (z-min)%5 >= 3和(z-min')%5==0，则F(min')< F(min)其中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

所以我们一起展示

如果5> (z-min)%5 >= 3和(z-min')%5==0，则F(min')< F(min)其中min'=min-x表示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将使用多一个操作到达min' = min-2，而每个操作10个将保存一个操作以获得min'。因此，我们只需增加10，直到它的数字(补偿)的“浪费”2：

P= 2,2,2,10,10,10,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结束；part博士！)

编辑的

OMG HACKERRANK上的测试用例很弱！

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

​

#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 +5，a2，a +5，a1，a1 +2，a2)

所以一切最终都正确了(我想.)当我删除行m = max(0, m);时，它允许min-x获得负的输出，并给出3作为一个正确的输出，当然，新代码也会得到ACed .