我在黑客级别上被问到了这一点,但我还没有找到一种解决方案,该解决方案并没有用完所分配的时间。我使用php,分配的时间为9秒...

这个想法是有一些票的“票摊”,比如说9。他们出售的任何票都是按照剩余的票数定价的,所以第一张票是9美元,第二张票是8美元,等等。

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

2 4
1 5

第一行包含两个数字:
  • 摊位数量
  • 出售了多少张票

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

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

    在这种情况下,您从第二档出售四张门票,价格为5 + 4 + 3 + 2 = $ 14

    那你怎么解决呢。我想出了两种方法,两种方法都用完了
  • 将停顿号(第二行)加载到数组中。遍历该阵列N次(要出售的票数),挑选出最大的数字,然后将其添加到聚合器中,从而减少该数字。这样,您就可以在汇总器中获得总计。
  • 将停顿号加载到数组中。对数组进行排序。向后遍历数组,然后执行以下操作:存储该数字(当前),将其添加到聚合器中,转到下一个值。如果相同(当前),则将其添加到聚合器,从中减去1,继续前进。如果不同,请返回数组末尾并重新开始。这样做N次(内部循环,而不是外部循环)。

  • 问题是:没有人工作。

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

    最佳答案

  • 创建一个数组,其中包含剩余门票数量的摊位数量。 (所以{0,3,0,2}表示2个档位有3张票,3个档位有1张票)
  • 递减最高的非零条目,递增其下方的条目,然后将该条目的索引添加到总数中。
  • 对每张售出的门票重复#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);
    

    10-07 19:38
    查看更多