java - 平等任务——算法设计

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 加到除 2 以外的所有数上得到 [3, 3, 7, 7, 11]

然后我们可以将 2 (4) 的两次加到除第 3 次以外的所有次数上，得到 [7, 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

让我建议减少问题。首先，让我们将三个选项参数化为一个:

Choose one colleague; give N chocolates to every other colleague, for N in {1, 2, 5}.

现在，对于减少:

Choose one colleague; give N chocolates to every other colleague, for N in {1, 2, 5}. Now, everyone eats exactly N chocolates.

转换为

Take N chocolates from any one colleague; for N in {1, 2, 5}. Negative totals are allowed.

这里的内存非常简单:它是 5、2、1 个单位硬币的找零问题。

你有一份Q巧克力数量的 list 。

• 任务:找到最少的交易数量来给每个人相同的数量。
• 子任务:找到 K 以最小化超过值 {Q[i] - K< 所需的硬币数量/strong>

观察:对于给定的面额，进行最小的更改是微不足道的:用 5 到用尽，然后用 2 到用尽，然后在需要时用 1。

引理:如果m是Q中的最小值，则K将在 [m-4, m]

范围内

算法

1. 找到m，Q的最小值
2. 对于 [m-4, m] 中的每个 K 值
   • 对于 Q 的每个元素，计算 Q - K 的硬币找零次数.
   • 对这些计数求和

您现在有五个总和；这五个中的最小值就是您的答案。