网站开发与设计现状,做网站用什么虚拟主机,深圳品牌公寓有哪些,怎样申请企业邮箱账号奶牛晒衣服
题目分析
这里出现了“弄干所有衣服的最小时间”#xff0c;那么可以考虑用二分去做。
第一阶段二段性分析
假设当前需要耗费的时间为mid分钟#xff0c;如果mid分钟内可以烘干这些衣服#xff0c;那么我们可以确定右边界大于mid的区间一定也可以。但是此时我…奶牛晒衣服
题目分析
这里出现了“弄干所有衣服的最小时间”那么可以考虑用二分去做。
第一阶段二段性分析
假设当前需要耗费的时间为mid分钟如果mid分钟内可以烘干这些衣服那么我们可以确定右边界大于mid的区间一定也可以。但是此时我需要找的是最短时间那么mid一定比大于mid的值更小所以大于mid的值我就不用管了也就是我可以确定我能够舍弃掉mid右边的值。我还想要确定比mid更小的值是否也满足条件所以我要在mid的左边继续二分。
if(check(mid)) {r mid;}//因为mid是符合条件的所以我要留着它而不是rmid-1假设当前需要耗费的时间为mid分钟如果mid分钟内不可以烘干这些衣服那么我们可以确定右边界小于mid的区间一定也不可以。所以小于mid的值我就不用管了也就是我可以确定我能够舍弃掉mid左边的值。我还想要找比mid更大的值是否可以满足条件所以我要在mid的右边继续二分。
else {l mid 1;}//因为mid是不符合条件的所以我不要留着它而不是lmid综上该题满足二段性可以用二分二分的板子就不说了接下来说一下check函数如何写。
第二阶段写check函数
check(mid)要实现的作用是检查能否在mid分钟内烘干这些衣服。对于一个衣服的湿度w[i]如果w[i]/a大于mid注意这里要采用函数实现上取整的话应该使用double类型所以在java里使用函数实现上取整时用 a ∗ 1.0 a*1.0 a∗1.0将整数类型转化为浮点数类型就需要使用烘干机使用的时间是(a[i]-mid*a)/ba是自然烘干每分钟可以减少的湿度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所以l0r1e9。
注意一个特殊情况如果k1那么其实烘干机有和没有都一样自然风干所需要的时间就是所有衣服中最大的湿度。
题目代码
#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 ab;for (int i 0; i n; i) {w[i] scan.nextInt();
// max Math.max(max, w[i]);}int l 0;int r 500005;while (lr){int mid(lr)/2;if(check(mid)){rmid;}else {lmid1;}}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;}
}
