无法理解算法

Question

这里的问题 https://www.hackerrank.com/challenges/equal

我看了它的编辑和无法理解它的链接。如果你没有对hackerrank做任何说明，那么你肯定不会看到它是社论，所以这里有一些社论。

这相当于说，克里斯蒂可以通过1,2或5，同时保持其它巧克力原封不动带走 一个同事的巧克力。
让我们考虑减少同事的巧克力作为一种手术。为了尽量减少操作次数，我们应该尽量使每个同事的巧克力数量等于组中最小巧克力的数量（分钟）。我们必须通过（A [i] - min）减少第i个人A [i]的巧克力数量。让这个值为x。

This can be done in k operations. 

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

，从这里我无法理解

设f（分钟）是操作和执行在所有的同事，以减少 他们的每一个巧克力到最小。但是，有时f（min）可能不会总是给出正确的答案 。它也可以是当

f(min) > f(min-1) 

f(min) < f(min-5) 

为f（分钟-5）开个运算多于F（分钟）其中，N是同事的数量 的情况。因此，如果

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

有人可以帮助我理解为什么这是必要的检查F（分钟），F（分-1），...，F（分-4）

Answer 1

考虑这种情况A = [1,5,5]

正如这篇社论说的那样，认为使用4（2减2）操作将A更改为[1,1,1]是最理想的，但最好将其更改为[ 0,0,0]与3（1减1，2减5）操作。

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

你不明白的部分是为了迎合这种情况，我们知道min可能不是最优的，因为min-x也许更好，但是x有多大？那么它是。社论说，如果我们知道x是最多4个，我们可以只是蛮力min,min-1 ... min-4来看看哪一个是最小的，而不会考虑太多。

推理（不证明！）对于x < = 4

如果x> = 5，这也是那么你必须至少使用额外的N型3（±5）操作上的所有元素绝对不是价值。

基本上它不是操作类型的问题，这是因为你需要对所有元素使用相同的操作，这样做之后，问题没有减少，元素之间的相对差异仍然是同时你的目标是使相对差异为0，你的成本为N操作为空。换句话说，如果x> = 5，那么x-5必须是更加优化的目标选择，确实x％5必须是最好的目标。

---

（下面是TL; DR部分：第2版）如果你是不是在证明

在写最初的解决方案的过程中有意跳转到最后一节，我怀疑X < = 2确实，我试图在HackerRank上提交一个代码，它只检查​​3210的最小值，然后它被ACed了。

更正式地，我要求

如果5>（Z-分钟）％5> = 3和（Z-MIN '）％5 == 0，则F（分钟'）< F（分钟） 其中min' =分钟-X对于x < = 2，F（K）=分钟＃为元素Z的操作成为ķ

（当心的符号，我使用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-分钟）％5> = 3和（Z-分钟 '）％5 == 0，则F（分钟'）< F（分钟） 其中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永远不能以使((z-min)%5 + x%5)%5 == 0

> =

如果x = 2，则（z-min）％5可以是3;如果x = 1，则（Z-分钟）％5可以是4，满足这两个条件：5> (z-min)%5 >= 3 and (z-min')%5==0

因此一起，我们表明

如果5>（Z-分钟）％5> = 3和（Z-MIN '）％5 == 0，则F（分钟'）< F（分钟） 其中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人将使用1次手术获得min' = min-2，而每10人将节省1次手术获得min'。所以我们只需要增加10个，直到它出数（补偿）2的“浪费”：

P = [2,2,2,10,10,10,10,10]，则f（min ）= 0 + 15 = 15，F（分钟-2）= 3 + 10 = 13

或只是简单地

P = [2,10,10]中，f（分钟）= 6，F（分钟-2）= 5

TL的（完;！DR一部分）

---

编辑

OMG HACKERRANK的测试用例很差！

故事是，当我今天早上到我的办公室，我一直在想这个问题了一下，认为有可能在我的代码（其中有一杆进洞！）

#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，与+5在[0 ]，a [2]，在[0]上的+5，在[1]上的a [1]，+2 ]，A [2]）

所以一切终于得到了正确的（我觉得...）当我删除行m = max(0, m);，它允许min-x获得负，得到3，正确的输出，当然还有新的代码得到ACed以及...