hackerrank算法的优化

Question

我在黑客运行k 上被问到这个问题，但我还没有想出一个不会运行超出分配时间的解决方案。我使用了 php 并且分配的时间是 9 秒...

想法是 "ticket stalls" 有一定数量的门票，比如 9 张。他们出售的任何门票都按照剩余的门票数量定价，因此第一张门票为 9 美元，第二张门票为 8 美元，依此类推。 ..

你得到两行数据，比如说：

2 4
1 5

第一行包含两个数字：

摊位数量
售出多少张票

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

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

在这种情况下，您以 5 + 4 + 3 + 2 = 14 美元的价格出售了 2 号摊位的四张票

那你是怎么解决的。我想出了两个办法，都运行没时间

将摊位号（第二行）加载到一个数组中。遍历该数组 N 次（要出售的门票数量），选出最大的数字，将其添加到聚合器中，减少该数字。然后你在聚合器中有总数。
将摊位号加载到数组中。对数组进行排序。向后遍历数组并像您一样：存储该数字（当前），将其添加到聚合器，转到下一个值。如果相同（当前），则将其添加到聚合器，从中减去 1，继续。如果不同，则回到数组的末尾重新开始。这样做 N 次（内部循环，而不是外部循环）。

问题：两者都不起作用。

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

Answer 1

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

Answer 2

让我们看看您的解决方案超时的原因。

Load the stall numbers (second line) into an array. Go through that array N times (the number of tickets to sell) picking the largest number out, adding it on to an aggregator, decreasing that number. Then you have the total in the aggregator.

这是O(N*M)，其中N是售票数量，M是售票亭数量。这几乎是一种蛮力方法，通常不足以击败 hackerrank 的测试。

Load the stall numbers into an array. Sort the array. Go backwards through the array and as you do: store that number (current), add it to the aggregator, go to the next value. If it is the same (current), then add it to aggregator, subtract 1 from it, keep going. If it is different, go back to the end of the array and start again. Do that N times (the internal loop, not the external one).

也许是我，但我不太明白你在这里的意思。据我所知，这听起来仍然是 O(N*M)。大量的ticket被多次减少导致你之前做的sort坏了怎么处理？

这里需要的是一个数据结构，可以高效的获取当前最大值，和可以高效的弹出/插入新元素。看起来最大堆是一个不错的选择。只需将每个展位的可用门票数量保持在最大堆中即可。要在 M 个摊位上出售 N 张门票，请执行 N 次：

提取最大值 - O(log(M))
将其添加到结果累加器 - O(1)
递减 - O(1)
将其插入堆中 - O(log(M))

总体复杂度为 O(N*log(M))，这可能是您能做的最好的了。

C++ 实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int max_revenue(vector<int> &tickets, int n) {

    make_heap(tickets.begin(), tickets.end());

    int res = 0;
    for (int i = 0; i < n; i++) {
        res += tickets.front();
        pop_heap(tickets.begin(), tickets.end());
        tickets[tickets.size()-1]--;
        push_heap(tickets.begin(), tickets.end());
    }

    return res;
}

int main(void) {
    int booths;
    cin >> booths;
    int n;
    cin >> n;

    vector<int> tickets(booths);
    for (int i = 0; i < booths; i++)
        cin >> tickets[i];

    cout << max_revenue(tickets, n) << endl;

    return 0;
}

Answer 3

MaxHeap 解决方案的小优化：

您不需要一张一张地删除门票。如果你有一个topwindow，你需要知道它有多少票，下一个有多少票。然后就可以去掉差价，一次算出总价。
如果您有多个 windows 具有相同的最大票数，您可以稍作修改。

Answer 4

这是 PHP 中的一个实现，它不会像其他一些答案那样创建额外的数组。总是有很多不同的方法来解决这个问题，看看这个，它可能会给你未来的想法。有很多方法可以在实际使用中改进它，但这只是为了展示快速解决问题的替代方法

class booth {

public $booths = [];
public $left = 0;
public $count = 0;
public $total = 0;
public $booth = 0;
public $nextBooth = 0;

function __construct() {
    $this->booths = [3, 7, 5, 2, 0, 2, 5, 15, 9, 1, 39, 91, 0, 58, 29];
    $this->left = 25;

    sort($this->booths);

    $this->booth = array_pop($this->booths);


    while($this->left > 0 && count($this->booths) > 0) {
        $this->count++;
        $this->nextBooth = array_pop($this->booths);        
        $this->countTotal($this->booth - $this->nextBooth);
    }

    // found end of array -- clear out any that are left
    if($this->left > 0)
        $this->countTotal(1);

    echo "total: " + $this->total."\r\n";
}

// everything global except loops
function countTotal($loops) {

    for($i = 0; $i < $loops, $this->left > 0; $i++) {
        if ($this->count > $this->left) 
            $this->count = $this->left;

        $this->total += $this->booth * $this->count;
        $this->left -= $this->count;
        $this->booth--;

    }
}

}

new booth();

Answer 5

如果你害怕 DP，这是你应该尝试的 O(n) 解决方案。以下代码仅考虑最大的元素并继续减少它直到我们达到所需的票数。它通过将倍增因子作为值存储在 hashMap 中来跟踪它。最后，如果票数大于所需票数，则从结果中减去最近添加的票价，直到票数等于所需票数。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TicketClass {
    public static void main(String[] args){
        int[] arr = {10,10,2,8,6,4};
        int ticket = 23;
        Arrays.sort(arr);
        int mul = 1;
        int k = 0;
        System.out.print("Hello World");
        long res = 0;
        Map<Integer,Integer> hm = new HashMap<>();
        for(int i:arr){
            if(hm.containsKey(i)){
                hm.put(i,hm.get(i)+1);
            }
            else
                hm.put(i,1);
        }

        int curr = arr[arr.length-1];

        while(k < ticket){
            mul=hm.getOrDefault(curr,mul);
            res += curr*mul;
            curr--;
            k += mul;
            if(hm.containsKey(curr))
                hm.put(curr,hm.get(curr)+mul);
        }

//End of while loop
        curr++;
        while(k > ticket){
            k--;
            res -=curr;
        }
        System.out.println("ticket "+k);
        System.out.println(res);
    }
}

hackerrank算法的优化

Optimization of a hackerrank algorithm

arrays

optimization

computer-science