1
class Solution {
2
  private long mod = 1000000007L;
3

4
  public int maxProfit(int[] inventory, int orders) {
5
    // we use pq to find the most balls
6
    PriorityQueue<Long> pq = new PriorityQueue<>((x, y) -> Long.compare(y, x));
7
    pq.offer(0L);
8

9
    // we use map to count the balls
10
    Map<Long, Long> map = new HashMap<>();
11
    map.put(0L, 0L);
12

13
    for (int j : inventory) {
14
      long i = (long) j;
15
      if (map.containsKey(i)) {
16
        map.put(i, map.get(i) + 1);
17
      } else {
18
        pq.offer(i);
19
        map.put(i, 1L);
20
      }
21
    }
22

23
    long res = 0;
24
    while (orders > 0) {
25
      long ball = pq.poll(), nextBall = pq.peek();
26
      long times = map.get(ball);
27
      long diff = Math.min(ball - nextBall, orders / times);
28
      if (diff == 0) {
29
        res = (res + orders * ball) % mod;
30
        break;
31
      }
32
      long sum = (ball * 2 + 1 - diff) * diff / 2 * times;
33
      res = (res + sum) % mod;
34
      orders -= diff * times;
35
      if (!map.containsKey(ball - diff)) {
36
        map.put(ball - diff, map.get(ball));
37
        pq.offer(ball - diff);
38
      } else {
39
        map.put(ball - diff, map.get(ball - diff) + map.get(ball));
40
      }
41
      map.remove(ball);
42
    }
43
    return (int) res;
44
  }
45
}