二分练习题——奶牛晒衣服

奶牛晒衣服

题目分析

这里出现了“弄干所有衣服的最小时间”，那么可以考虑用二分去做。

第一阶段二段性分析

假设当前需要耗费的时间为mid分钟，如果mid分钟内可以烘干这些衣服，那么我们可以确定右边界大于mid的区间一定也可以。但是此时我需要找的是最短时间，那么mid一定比大于mid的值更小，所以大于mid的值我就不用管了，也就是我可以确定我能够舍弃掉mid右边的值。我还想要确定比mid更小的值是否也满足条件，所以我要在mid的左边继续二分。

if(check(mid)) {r = mid;}//因为mid是符合条件的，所以我要留着它，而不是r=mid-1

假设当前需要耗费的时间为mid分钟，如果mid分钟内不可以烘干这些衣服，那么我们可以确定右边界小于mid的区间一定也不可以。所以小于mid的值我就不用管了，也就是我可以确定我能够舍弃掉mid左边的值。我还想要找比mid更大的值是否可以满足条件，所以我要在mid的右边继续二分。

else {l = mid + 1;}//因为mid是不符合条件的，所以我不要留着它，而不是l=mid

综上该题满足二段性，可以用二分，二分的板子就不说了，接下来说一下check函数如何写。

第二阶段写check函数

check(mid)要实现的作用是检查能否在mid分钟内烘干这些衣服。对于一个衣服的湿度w[i]，如果w[i]/a大于mid（注意这里要采用函数实现上取整的话，应该使用double类型，所以在java里使用函数实现上取整时，用$a\ast 1.0$将整数类型转化为浮点数类型），就需要使用烘干机，使用的时间是(a[i]-mid*a)/b，a是自然烘干每分钟可以减少的湿度，b是烘干机烘干每分钟额外减少的湿度。因为烘干衣服不足1分钟也要按一分钟算，所以这里要上取整。

java

static boolean check(int mid){
    long s = 0;
    for (int i = 0; i < n; i++) {
        if (Math.ceil(w[i]/(a*1.0))>mid){
            s += Math.ceil((w[i]-a*mid)/(b*1.0));
        }
    }
    return s <= mid;
}

c++

//这里的w[i]+a-1和w[i] - a * x + b - 1，即比正常多出来的+a-1和+b-1都是为了实现上取整。
bool check(int x){
	long sum = 0;
	for (int i = 0; i < n; i ++){
		if ((w[i]+a-1) / a <= x)
			continue;
        sum += (w[i] - a * x + b - 1) / b;
	}
	if (sum <= x)
		return true;
	else return false;
}

第三阶段二分范围确定

烘干的时间最长就是不使用烘干机，自然风干需要a[i]分钟，而a[i]最大是1e9，所以l=0，r=1e9。

注意一个特殊情况，如果k=1，那么其实烘干机有和没有都一样，自然风干所需要的时间就是所有衣服中最大的湿度。

题目代码

#include <iostream>
#include <stdbool.h>
#define N 500010

int n, a, b;
int w[N];

bool check(int x){
	long sum = 0;
	for (int i = 0; i < n; i ++){
		if ((w[i]+a-1) / a <= x)
			continue;
        sum += (w[i] - a * x + b - 1) / b;
	}
	if (sum <= x)
		return true;
	else return false;
}
int main(){
	scanf("%d%d%d",&n, &a, &b);
	for (int i = 0; i < n; i ++){
		scanf("%d", &w[i]);
	}
	int l = 0;
	int r = 5e5 + 5;
	while (l < r){
		int mid = (l + r) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	printf("%d", l);
	return 0;
}

import java.util.Scanner;
public class Main{
    static int a;
    static  int b;
    static int n;
    static int[] w;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        w = new int[n];
        a = scan.nextInt();
        b = scan.nextInt();
//       int max = a+b;
        for (int i = 0; i <n; i++) {
                w[i]= scan.nextInt();
//            max= Math.max(max, w[i]);
        }
        int l = 0;
        int r = 500005;
        while (l<r){
            int mid=(l+r)/2;
            if(check(mid)){
                r=mid;
            }else {
                l=mid+1;
            }
        }
        System.out.println(l);
    }
    static boolean check(int mid){
        long s = 0;
        for (int i = 0; i < n; i++) {
            if (Math.ceil(w[i]/(a*1.0))>mid){
                s += Math.ceil((w[i]-a*mid)/(b*1.0));
            }
        }
        return s <= mid;
    }
}