平等任務 - 算法設計

Question

我試圖解決平等問題https://www.hackerrank.com/challenges/equal/problem

這裏是我的代碼

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 


public class Solution { 
    static List<Integer> memo = new ArrayList<Integer>(); 

    public static void main(String args[]) throws Exception { 
     Scanner in = new Scanner(System.in); 
     int test = in.nextInt(); 
     int n = in.nextInt(); 
     //we initialize a list of memoized values for ho many 1,2,5 choccolates we need to get 1 ... 100 
     /* 
     we have 1, 2 and 5 to add 
     if k<=2 then k=1 
     if k>2 and k<5 then n[k] = n[k-2]+1 
     if k==5 then k=1 
     if k > 5 then n[k] = n[k-5]+1 
     */ 
     memo.add(1); 
     memo.add(1); 
     for (int i=0;i<100;i++){ 
      if(i==4){ 
       memo.add(1); 
      } 
      if(i>1 && i<4){ 
       memo.add(memo.get(i-2)+1); 
      } 
      if(i>4){ 
       memo.add(memo.get(i-5)+1); 
      } 
     } 
     //System.out.println(memo.toString()); 
     for (int i=0;i<test;i++){ 
      int val[] = new int[n]; 
      for (int j=0;j<n;j++){ 
       val[j]=in.nextInt(); 
      } 
      //we sort the values in order to start from the minimum 
      Arrays.sort(val); 
      //System.out.println(Arrays.toString(val)); 
      calculateOperations(val); 

     } 
    } 

    //we extend at runtime the memoized values if they are not enough 
    public static int computeCount(int val){ 
     if(val==0){ 
      return 0; 
     } 
     int ml = memo.size(); 
     if(val<=ml){ 
      return memo.get(val-1); 
     }else{ 
      for (int i=ml-1;i<val;i++){ 
      if(i==4){ 
       memo.add(1); 
      } 
      if(i>1 && i<4){ 
       memo.add(memo.get(i-2)+1); 
      } 
      if(i>4){ 
       memo.add(memo.get(i-5)+1); 
      } 
      } 
      return memo.get(val-1); 
     } 
    } 


    // 1 1 3 5 9 
    // 2 2 4 6 9 

    public static int [] addChoccolate(int [] values,int val,int no){ 
     for (int k=0;k<values.length;k++){ 
      if(k!=no){ 
      values[k] = values[k]+val; 
      } 
     } 
     return values; 
    } 

    public static int findDelta(int [] values){ 
     int s1 = values[0]; 
     for (int k=1;k<values.length;k++){ 
      if(values[k]!=s1){ 
       return k; 
      } 
     } 
     return 0; 
    } 

    public static void calculateOperations(int val[]){ 
     int count =0; 
     int delta = findDelta(val); 
     while(delta>0){ 
      count += computeCount(val[delta]-val[0]); 
      val = addChoccolate(val,val[delta]-val[0],delta); 
      //System.out.println(Arrays.toString(val)); 
      Arrays.sort(val); 
      delta = findDelta(val); 
     } 
     System.out.println(count); 
    } 
} 

它適用於輸入

1 
5 
1 3 5 5 9 

實際上它打印出來8這是正確的，因爲它可以表明，從起始狀態

[1,3,5,5,9]我們可以加2除了第二，然後得到[3，3，7，7，11]

然後我們可以添加兩次2（4）給所有但是第3個並得到[7,7,11,15]

然後我們可以添加兩次2（4）除了第4次，所有[11,11,11,11,19]

最後加1次5，一次2和一個時間1（8）所有，但最後一個[19，19，19，19，19]

總結應用這些操作我們得到：

1 +2 +2 + 3 = 8

然而：我不明白爲什麼它不會爲HackerRank工作測試

Answer 1

讓我提出一個減少的問題。首先，讓我們將三個選項參數化爲一個：

選擇一個同事;在{1,2,5}中給予N巧克力給所有其他同事， 。現在

，爲減少：

選擇一個同事;給N巧克力給其他每個同事， 爲N在{1,2,5}中。現在，大家正好吃否巧克力。

它轉換到

採取n的任一項同事巧克力;對於{1，2，5}中的N。負數總和是允許的。

在這裏記憶很簡單：這是5,2,1單位硬幣的硬幣更換問題。

你有一個清單問巧克力數量。

• 任務：找到最少數量的交易給每個人相同的數量。
• 子任務：找到ķ以最小化需要的所有的值，硬幣的數量{Q [Ⅰ] - ķ}

觀察：與給定的面額，使得最小的變化是微不足道的：使用5來消耗，然後使用2來消耗，如果需要的話使用1。

引理：如果米是Q最小值，ķ將在範圍[米 -4，米]

算法

1. 查找米，的Q
2. 最小值對於的ķ每個值[米 -4，米]
   • 對於Q每個元素，計算硬幣更換計數Q - K。
   • 和那些數

你現在有五種款項;這五個中的最小值就是你的答案。

Answer 2

我想我現在已經對問題有了一個清晰的認識，我會盡量以最簡單的方式寫下來。

正如@Prune所提到的，除了第i個元素之外，都意味着從第i個元素中減去。

另外考慮到這裏的重點是讓所有的個人都達到同樣的價值。

現在，如果我們按照遞增的方式對元素進行排序，我們可能希望找到最小的步數（減1,2,5），以便將每個個體都取爲第一個（最小可能）的值。

但是，這有時會導致次優解決方案。讓我舉一些例子：

如果我們從[1 3 6]開始，我們可以從第二個元素中減去2並轉到[1 1 6]，然後我們可以減去5到第三個並轉到[1 1 1 ]。在這種情況下，解決方案是2並且是正確的。

然而，在這種情況下[1 5 5]，我們需要從第二個和第三個元素中減去2次2以獲得[1 1 1]。在這種情況下，解決方案將是4個步驟。但這不是最低的可能。 可能的最小值實際上是從第一個元素中移除1並轉到[0 5 5]，然後從第二個元素和第三個元素中移除5個總共3個步驟。這是正確的。

這是因爲我們需要一個步驟來減去5，但我們需要兩個步驟來移除3和4個巧克力。

所以這裏的想法是我們可能需要從最小元素（值[0]）中刪除'something'，以便使列表中遠離它的倍數的元素數量最大化。

這東西多少錢？我們不知道，所以我們需要用values[0]= values[0], values[0]=values[0]-1, values[0]=values[0]-2, values[0]=values[0]-3, values[0]=values[0]-4評估所有可能性。 我們只需要從0刪除到4，因爲我們一定會找到5乘數。

考慮例如[1 9 9]如果我們不減去任何東西到第一個元素，我們需要從第二個和第三個減去1,2,5（8），這意味着6個步驟。如果我們嘗試使用值[0] =值[0] -1，我們有[0 9 9]，這意味着從第二個和第三個減去2,2,5（9），這也意味着6步加1（從第一個減法），所以7個步驟。 但是，如果我們嘗試使用值[0] =值[0] -2，我們有[-1 9 9]。在這種情況下，我們只需要從第二個和第三個元素中減去5（10）的兩倍以得到[-1 -1 -1]。這意味着4步加1（前2減），所以5步是最好的解決方案。