HackerRank上两个栈博弈的正确算法

Question

在每次移动中，Nick可以从堆栈A或B堆栈的顶部移除一个整数。

Nick保存从两个堆栈中移除的整数的运行和。

如果Nick在任何一点上的运行和大于游戏开始时给定的某个整数X，他将被取消比赛资格。

Sample Input 0

1 -> Number of games
10 -> sum should not exceed 10 
4 2 4 6 1  -> Stack A
2 1 8 5 -> Stack B

Sample Output 

4

1
67
19 9 8 13 1 7 18 0 19 19 10 5 15 19 0 0 16 12 5 10 - Stack A
11 17 1 18 14 12 9 18 14 3 4 13 4 12 6 5 12 16 5 11 16 8 16 3 7 8 3 3 0 1 13 4 10 7 14 - Stack B

我不明白算法，它看起来像DP，对我来说，有人能帮助我的方法/算法吗？

**

public class Default {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numOfGames = Integer.parseInt(br.readLine());
        for (int i = 0; i < numOfGames; i++) {
            String[] tmp = br.readLine().split(" ");
            int numOfElementsStackOne = Integer.parseInt(tmp[0]);
            int numOfElementsStackTwo = Integer.parseInt(tmp[1]);
            int limit = Integer.parseInt(tmp[2]);
            int sum = 0;
            int popCount = 0;

            Stack<Integer> stackOne = new Stack<Integer>();
            Stack<Integer> stackTwo = new Stack<Integer>();

            String[] stOne = br.readLine().split(" ");
            String[] stTwo = br.readLine().split(" ");

            for (int k = numOfElementsStackOne - 1; k >= 0; k--) {
                stackOne.push(Integer.parseInt(stOne[k]));
            }

            for (int j = numOfElementsStackTwo - 1; j >= 0; j--) {
                stackTwo.push(Integer.parseInt(stTwo[j]));
            }

            while (sum <= limit) {
                int pk1 = 0;
                int pk2 = 0;
                if (stackOne.isEmpty()) {
                    sum = sum + stackTwo.pop();
                    popCount++;
                } else if (stackTwo.isEmpty()) {
                    sum = sum + stackOne.pop();
                    popCount++;
                } 
                else if (!stackOne.isEmpty() && !stackTwo.isEmpty()) {
                    pk1 = stackOne.peek();
                    pk2 = stackTwo.peek();

                    if (pk1 <= pk2) {
                        sum = sum + stackOne.pop();
                        popCount++;
                    } else {
                        sum = sum + stackTwo.pop();
                        popCount++;
                    }
                } else if(stackOne.isEmpty() && stackTwo.isEmpty()){
                    break;
                }
            }

            int score = (popCount>0)?(popCount-1):0;
            System.out.println(score);
        }
    }
}

Answer 1

好的，我将尝试解释一个算法，基本上可以用O(n)解决这个问题，你需要尝试自己编码。

我会用一个简单的例子来解释，你可以反映出来

1 -> Number of games
10 -> sum should not exceed 10  
4 2 4 6 1  -> Stack A
2 1 8 5 -> Stack B

首先您需要创建2个数组，数组将包含所有数的总和，直到它的堆栈索引，例如，对于堆栈A，您将有以下数组

4 6 10 16 17  //index 0 ->4

2 3 11 16

a = 1 1 1 211 2
b = 1 85

a' = 1 2 3 214 216
and b' = 1 86
current sum = 86+216 > 217

216/5~43.2` and `86/2=43`, 

所以我们在a‘中移动指针。但是，这并不能解决问题--“

214+86 is still > 217!!` 

如果我们移除86个，会更好！因此，我们应该继续删除与前一个元素有较大差异的元素！

如果两个值都相等，则顺理成章地移动与前一个值有较大差异的值上的索引（请记住，我们是以相反的顺序移动索引）。