养鸡场还有多少只鸡？ - 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;
    }
}