養雞場還有多少隻雞？ - Java - PriorityQueue，大頂堆

小強有

n

個養雞場，第

i

個養雞場初始有

a[i]

隻小雞。與其他養雞場不同的是，他的養雞場每天增加

k

隻小雞，小強每天結束都會在數量最多的養雞場裡賣掉一半的小雞，假如一個養雞場有

x

隻雞，則賣出後隻剩下

x/2

(向下取整)隻雞。問

m

天後小強的

n

個養雞場一共多少隻小雞？

輸入 第一行輸入三個

int

類型

n,m,k（1 <= n,m,k <= 10^6）

第二行輸入

n

個正整數，表示

n

個養雞場初始雞的個數

輸出 輸出一個整數表示雞的總數

示例 輸入：

3 3 100
100 200 400
           

輸出：

題解

正常計算方法：

操作	最多的雞場雞數	最少的雞場雞數
初始雞數	400	200	100
加100	500	300	200
賣250	300	250	200
加100	400	350	300
賣200	350	300	200
加100	450	400	300
賣225	400	300	225

最後還有 925 隻雞

優化的計算方法：

操作	最多的雞場雞數	最少的雞場雞數	一個雞場的增量
初始雞數	400	200	100
100
賣250	200	150	100
200
賣200	150	100
300
賣225	100	-75

最後還有 300×3+100+0-75=925 隻雞

300表示一個雞場總的增加數量

3表示雞場個數

通過減少不斷增加 k 這個重複操作達到優化的目的。

Java代碼

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {
    public static int chickenFarm(int n, int m, int k, int[] a) {
        // PriorityQueue預設是小頂堆，此處将參數改為大頂堆
        Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        // 儲存養雞場原始的雞的數量
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            queue.offer(a[i]);
            sum += a[i];
        }
        // 每個養雞場增加的雞數
        int incremental = 0;
        for (int i = 0; i < m; ++i) {
            incremental += k;
            // 雞最多的養雞場的雞數
            int max = queue.poll();
            // 這個養雞場當天賣掉的雞數，+優先級高于>>
            int reduced = max + incremental + 1 >> 1;
            // 剩餘的雞數放回堆裡
            queue.offer(max - reduced);
            // 原始的雞數減少
            sum -= reduced;
        }
        // 此時 incremental = k × m，sum表示原始的剩餘的雞數
        return incremental * n + sum;
    }
}