我在黑客级别上被问到了这一点,但我还没有找到一种解决方案,该解决方案并没有用完所分配的时间。我使用php,分配的时间为9秒...
这个想法是有一些票的“票摊”,比如说9。他们出售的任何票都是按照剩余的票数定价的,所以第一张票是9美元,第二张票是8美元,等等。
您将获得两行数据,例如:
2 4
1 5
第一行包含两个数字:
第二行包含每个摊位最初有多少张票的列表,因此在这种情况下,摊位1有1张票,摊位2有5张票。
问题:出售给定数量的门票最多可以赚多少钱?
在这种情况下,您从第二档出售四张门票,价格为5 + 4 + 3 + 2 = $ 14
那你怎么解决呢。我想出了两种方法,两种方法都用完了
问题是:没有人工作。
谁能想到更好的解决方案?
最佳答案
还有一种明显的方法,可以通过乘以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);