题面:游客们在苏门答腊岛游玩,突然接收到紧急通知,
岛上火山即将喷发。在此干钧一发时刻,上帝同情
受难的游客,赠与他们超能力。
他们每秒可以移动17米,且拥有一定数量的魔法
值。拥有魔法值的游客可以1秒内顺时移动60米,但
是每次都需要消耗魔法值10点。
与此同时,如果某一秒游客选择原地不动,那么魔
法值可以增长4点。
假设游客们需要在规定时间T秒逃离到距离他们D米
的安全地带方可以保住性命,请判断游客是否能够
逃离到安全区域。
给你初始魔法值M,安全地带距离D,规定时间T,请你计算他们能否逃离。
若能逃离,输出最短逃脱时间,若不能,输出最长逃脱长度。
解法:二分。
package com.sky;import java.util.Scanner;public class Test1 {private static long maxDistance(long t, long M) {long maxK = (M + 4 * t) / 14;for (long k = maxK; k >= 0; k--) {long requiredMagic = 10 * k;long s;if (requiredMagic > M) {s = (requiredMagic - M + 3) / 4;} else {s = 0;}if (s + k > t) {continue;}long m = t - k - s;if (m < 0) {continue;}return 60 * k + 17 * m;}return 17 * t;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);long M = sc.nextLong();long D = sc.nextLong();long T = sc.nextLong();long low = 0, high = T, ans = -1;while (low <= high) {long mid = low + (high - low) / 2;long dist = maxDistance(mid,M);if (dist >= D) {ans = mid;high = mid - 1;} else {low = mid + 1;}}if (ans != -1 && ans <= T){System.out.println("YES " + ans);}else System.out.println("NO " + maxDistance(T,M));}
}