输入：
输入t表示案例数
输入n，w分别表示手机数和充电器功率
接下来的n行输入 a[i] b[i]表示每一部手机初始电量，和每一秒消耗的电量
输入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) 回帖