無法理解算法

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以及...