优化黑客算法

Question

我在黑客等级上被问到了这一点,我还没有找到一个没有用完规定时间的解决方案.我使用php并且分配的时间是9秒......

这个想法是有"门票摊位"和一定数量的门票,比如9门票.他们卖的任何门票都是以剩余的门票数量为准,所以第一张门票是9美元,第二张是8美元等等.

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

2 4
1 5

第一行包含两个数字:

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

第二行包含每个档位最初有多少票的列表,因此在这种情况下,档位1有1张票,档位2有5张票.

问题:出售给定票数的最高金额是多少？

在这种情况下,您从摊位2出售4张门票,价格为5 + 4 + 3 + 2 = 14美元

那你怎么解决呢 我想出了两种方法,两种方式都用完了

1. 将停转数(第二行)加载到数组中.通过该阵列N次(销售门票的数量)选择最大数量,将其添加到聚合器,减少该数量.然后你在聚合器中有总数.

2. 将停转数加载到一个数组中.对数组进行排序.向后遍历数组并执行:存储该数字(当前),将其添加到聚合器,转到下一个值.如果它是相同的(当前),则将其添加到聚合器,从中减去1,继续.如果不同,请返回到数组的末尾并重新开始.做N次(内部循环,而不是外部循环).

问题:没有人工作.

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

Answer 1

1. 创建一个数组，其中包含剩余门票数量的摊位数量。（所以{0, 3, 0, 2}表示2个摊位有3张票，3个摊位有1张票）
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);