腾讯笔试4.4第四题充电问题优先队列加数学计算ac

输入：

输入t表示案例数
输入n，w分别表示手机数和充电器功率
接下来的n行输入 a[i] b[i]表示每一部手机初始电量，和每一秒消耗的电量

输出：用充电器给这些手机轮流充电（不计切换时间），最多可以撑多久。

样例：

3 5

3 6

2 5

1 6

有三部手机，充电功率为5，可以以时间为横轴，剩余电量为纵轴画出这样的图：

可以看到最快用完电的手机是（1，6），没有充电器的话，答案就是1/6

在有充电器的情况下，我们可以减小每条线的斜率（通过充电降低手机的掉电速度）

问题转变成了如何合理分配充电器的功率（之所以能分配功率是因为充电器可以反复横跳😁），让这些手机中最早用完电的时间尽可能晚一些。

先给最拉垮的1号手机分配点功率，让1号的耗尽时间与2号的耗尽时间同步（0.4s），再同时给1号2号分配功率，直到它们与3号手机同步..........

重复此过程直到我们把充电器的功率彻底用完，最后输出这个耗尽时间。

当然功率够的话可以把所有斜率拨正。这时就输出-1

最后附上当时ac的代码。


import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i = 0; i < T; i++) {
            int n = sc.nextInt();
            double w = sc.nextDouble();
            PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> (int) (a[0] * b[1] - a[1] * b[0]));
            for(int j = 0; j < n; j++) {
                pq.offer(new double[]{sc.nextInt(), sc.nextInt()});
            }
            while(w > 0) {
                if(pq.size() == 1) {
                    double[] cur = pq.poll();
                    if(cur[1] <= w) {
                        System.out.println(-1);
                        w = 0;
                    } else {
                        System.out.println(cur[0]/(cur[1] - w));
                        w = 0;
                    }
                } else {
                    double[] cur = pq.poll();
                    double[] next = pq.peek();
                    double temp = (next[0] * cur[1] - cur[0] * next[1]) / next[0];
                    if(w  > temp) {
                        w -= temp;
                        pq.poll();
                        pq.offer(new double[]{cur[0] + next[0], cur[1] + next[1] - temp});
                    } else if(w <= temp) {
                        System.out.println(cur[0]/(cur[1] - w));
                        w = 0;
                    }
                }
            }
        }
    }
}

#笔试题目##腾讯#