同时运行N台电脑的最长时间

在这里插入图片描述

求解代码

maxRunTime方法

假设所有电池的最大电量是max，如果此时sum>(long)max*num，那么最终的供电时间一定会大于等于max，由此也能推出最终的答案为sum/num。

对于sum<=(long)max*num的情况，在0~max区间内不断二分查找即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


	public static long maxRunTime(int num,int[] arr){
		int max = 0;
		long sum = 0;
		for(int x:arr){
			max = Math.max(max,x);
			sum+=x;
		}

		if(sum>(long)max*num){
			return sum/num;
		}

		int ans = 0;
		for(int l=0,r=max,m;l<=r;){
			m= l+((r-l)>>1);
			if(f(arr,num,m)){
				ans = m;
				l = m+1;
			}else{
				r=m-1;
			}
		}
		return ans;
	}

f方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


	public static boolean f(int[] arr, int num, int time) {
		long sum = 0;
		for (int x : arr) {
			if (x > time) {
				num--;
			} else {
				sum += x;
			}
			if (sum >= (long) num * time) {
				return true;
			}
		}
		return false;
	}