首页 > 腾讯笔试4.4第四题充电问题优先队列加数学计算ac
头像
(--)nnn
编辑于 2021-04-18 13:54
+ 关注

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

输入:
输入t表示案例数
输入n,w分别表示手机数和充电器功率
接下来的n行输入 a[i] b[i]表示每一部手机初始电量,和每一秒消耗的电量
输出:用充电器给这些手机轮流充电(不计切换时间),最多可以撑多久。

样例:
1
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;
                    }
                }
            }
        }
    }
}


全部评论

(8) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐