Ticket

Ticket.java

import java.lang.reflect.Array;
import java.util.*;

/**
 * Created by pyq on 4/10/15.
 */
public class Ticket {
    // has n stations, every station has stations[i] number tickets, and sell with station[i] price
//    public static long maxProfit(int[] stations, int n, int m) {
//        Queue<Integer> maxHeap = new PriorityQueue<>(n, new Comparator<Integer>(){
//            @Override
//            public int compare(Integer a, Integer b) {
//                return b - a;
//            }
//        });
//        for(int ticket : stations) {
//            if (ticket > 0 && ticket < 10000) {
//                maxHeap.offer(ticket);
//            }
//        }
//        long maxProfit = 0;
//        int i = 0;
//        while (!maxHeap.isEmpty() && i < m) {
//            int sell = maxHeap.poll();
//            maxProfit += sell;
//            i++;
//            if (sell > 0) {
//                maxHeap.offer(sell - 1);
//            }
//        }
//        return maxProfit;
//    }

    public static long maxProfit1(int[] stations, int n, int m) {
        Arrays.sort(stations);
        //max is at end;
        int i = n - 1;
        long profit = 0;
        while (m > 0) {
            //find the first max
            while (i > 0 && stations[i] == stations[i - 1]) {
                i--;
            }
            //sell at one time with price: stations[i] max price
            int count = n - i;
            if (count <= m) {
                profit += count * stations[i];
                stations[i]--;
                m -= count;
            } else {
                profit += m * stations[i];
                break;
            }
        }
        return profit;
    }
    public static void main(String[] args) {
       // System.out.println(maxProfit(new int[]{10000, 10000}, 2, 2000));
        System.out.println(maxProfit1(new int[]{10000, 10000}, 2, 2000));
       // System.out.println(maxProfit(new int[]{100000, 100000, 100000, 100000, 99999}, 5, 500000));
        System.out.println(maxProfit1(new int[]{100000, 100000, 100000, 100000, 99999}, 5, 500000));
    }
}

//example
/*[10,7,5,3], m = 20, n为length
sort => 3 5 7 10
 maxIndex = 3
 1. 对于这次取票 price 最高可以卖 price[maxIndex] 10, 一共有 n - maxIndex 个这样值为price[maxIndex]的站
 所以我们可以对于此次操作 卖  price[maxIndex] *  n - maxIndex
 profit += 10 * 1
 然后讲maxIndex站的票-1
 之后maxIndex 没变 还是最后一个值
 类似操作
 profit += 9 * 1
 profit += 8 * 1
 2. 现在 [3, 5, 7, 7]
    现在我们要更新maxIndex， 为 n - 2 (作用是用来标记有多少个值为max的station， 这里的maxIndex 为第一个最大值)
    现在 对于票价为 7的，我们可以卖两张
    之后更新其实应该 都减一， 但是我只用price[maxIndex] 表示所有max的值，就price[maxIndex]--， 
    而不用for(i : maxIndex to n - 1) price[i]--
 */