本文主要是介绍POJ3104 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
有n件湿衣服，含水量分别为a[0~n-1],烘干机每分钟可以除去k份水，每过一分钟每件衣服自动蒸发1份水，注意在烘干的时候不会自动蒸发水
要点：
1.注意会超int，所以用long long（这里WA了很多次）
2.一个小技巧，整数运算中，a/b的上取整可以用（a+b-1）/b。
3.用二分枚举mid，如果一件衣服水量大于mid时，最短的时间是自动蒸发mid分钟，在烘干一段时间，为了将正在烘干的衣服也进入模型，采用(a[i]-mid)/(k-1),k-1中1是已经自然蒸发的量。这样把所有时间加起来比较即可
#include<stdio.h>
#include<string.h>
#define maxn 100000+5
int a[maxn];
int n, k;bool check(long long mid)
{int i;long long num = 0;for (i = 0; i < n; i++){if (a[i] - mid <= 0)//小于等于直接自动蒸发即可，不用烘干continue;if (k == 1) //k=1直接退出循环看上面一步return false; //只有刚好n个都小于等于mid时可以得到true得出结果num += (a[i] - mid+k-2) / (k-1);//向上取整的小技巧} if (num > mid) //从num+=a[i]-mid看，sum大了说明mid小了return false;elsereturn true;//sum小了说明mid开大了
}int main()
{ while (scanf("%d", &n) != EOF){int i;long long left=0, right=0,mid; //注意容易超intfor (i = 0; i < n; i++){scanf("%d", &a[i]);right += a[i];}scanf("%d", &k);long long step=0;while (left <= right){mid = (left + right) / 2;if (check(mid)){right = mid - 1;step = mid;}else left = mid + 1;}printf("%I64d\n", step);}return 0;
}这篇关于POJ3104 二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
