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

奶牛晒衣服

题目分析

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

第一阶段二段性分析

假设当前需要耗费的时间为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 500010int 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;elsel = 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;}
}