arrays - Hackerrank算法的优化

Question

有人问我这个关于黑客等级的问题，但我还没有找到一个没有超出规定时间的解决方案。我使用 php，分配的时间是 9 秒...

这个想法是有一定数量的票的“票摊”，比如 9 张。他们出售的任何票都是按照剩余票数定价的，所以第一张票是 9 美元，第二张票是 8 美元，依此类推...

您将获得两行数据，例如:

2 4
1 5

第一行包含两个数字:

1. 摊位数量
2. 售出多少张门票

第二行包含每个摊位最初拥有多少张门票的列表，因此在本例中，摊位 1 有 1 张门票，摊位 2 有 5 张门票。

问题:出售给定数量的门票最多可以赚多少钱？

在本例中，您从 2 号摊位出售四张门票，价格为 5 + 4 + 3 + 2 = 14 美元

那怎么解决呢。我想了两种办法，都没有时间

1. 将摊位编号(第二行)加载到数组中。遍历该数组 N 次(要出售的门票数量)，选出最大的数字，将其添加到聚合器中，从而减少该数字。然后您就可以在聚合器中获得总数。

2. 将摊位编号加载到数组中。对数组进行排序。向后遍历数组，就像您所做的那样:存储该数字(当前)，将其添加到聚合器，转到下一个值。如果相同(当前)，则将其添加到聚合器，从中减去 1，继续。如果不同，则返回到数组末尾并重新开始。这样做 N 次(内部循环，而不是外部循环)。

问题是:两者都不起作用。

谁能想到更好的解决方案吗？

Answer 1

1. 创建一个包含剩余门票数量的摊位数量的数组。 (所以 {0, 3, 0, 2} 表示 2 个摊位有三张票，3 个摊位有一张票)
2. 减少最高的非零条目，增加其下方的条目，并将该条目的索引添加到总数中。
3. 每售出一张门票，请重复 #2 一次。

还有一个明显的方法可以通过乘以 MIN(最高摊位的计数，剩余待售票)来改进这一点。

注意:为了使其性能良好，您的实现语言必须具有真正的数组(即，无论索引如何，访问时间恒定)。我不懂PHP，但有些语言(JS？)使用顺序列表来模仿数组，但没有相同的性能。

<小时/>

下面是上述方法的 Java 实现(阅读注释以更好地理解):

        int[] stalls = new int[] { 4, 7, 1, 4, 8, 8 };
        int t = 4;

        Arrays.sort(stalls);

        int tickets = stalls[stalls.length - 1];
        int[] dp = new int[tickets + 1];

        for (int i = 0; i < stalls.length; i++) {
            dp[stalls[i]]++;
        }

        int total = 0;
        int i = dp.length - 1;

        while (t > 0) {
            if (dp[i] > 0) {
                total += i;
                t--;
                dp[i]--;
                dp[i - 1]++;
            } else {
                i--;
            }
        }

        System.out.println(total);