2015年10月1日星期四

卖车票

比如有5个窗口,[4, 3, 2, 5, 1],代表第一个窗口有4张票,第二个窗口3张...当m = 4时,代表我想卖3张票子,怎么卖这四张票可以得到最大的profit呢。
第一张票应该是第四个窗口卖,5刀,然后array就变成[4, 3, 2, 4, 1],因为第四个窗口卖掉了一张。
第二张票应该在第一个或者第四个窗口卖,因为它们都是四刀票,我们就在第一个窗口卖,array就变成[3, 3, 2, 4, 1]。
第三张票应该在第四个窗口卖,卖四刀,卖完后array就变成[3, 3, 2, 3, 1]
第四张票应该在第一个第二个或者第四个窗口卖,卖3刀,假设我们在第一个窗口卖,买完后array变成[2, 3, 2, 3, 1
返回的总profit就是5 + 4 + 4 + 3 = 16

private int sellTicket(int[] nums, int amount) {
    PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
    public int compare(Integer n1, Integer n2) {
    return n2.intValue() - n1.intValue();
    }
    });
    for (int n : nums) {
    queue.add(n);
    }
    int res = 0;
    while (amount-- > 0) {
    int val = queue.poll();
    res += val;
    if (val > 1) {
    queue.add(val - 1);
    }
    }
    return res;
    }

没有评论:

发表评论