本文主要是介绍poj 3104 二分答案，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
n件湿度为num的衣服，每秒钟自己可以蒸发掉1个湿度。
然而如果使用了暖炉，每秒可以烧掉k个湿度，但不计算蒸发了。
现在问这么多的衣服，怎么烧事件最短。
解析：
二分答案咯。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);
const int maxn = 100000 + 10;LL num[maxn];
LL k;
int n;bool ok(LL x)
{LL cnt = 0;for (int i = 0; i < n; i++){if (x < num[i]){LL t = ceil((num[i] - x) * 1.0 / (k - 1));cnt += t;}}return cnt <= x;
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d", &n)){LL maxV = 0;for (int i = 0; i < n; i++){scanf("%lld", &num[i]);maxV = maxV < num[i] ? num[i] : maxV;}scanf("%lld", &k);if (k == 1){printf("%lld\n", maxV);continue;}LL lo = 1, hi = maxV;LL ans;while (lo <= hi){LL mi = (lo + hi) >> 1;if (ok(mi)){hi = mi - 1;ans = mi;}elselo = mi + 1;}printf("%lld\n", ans);}return 0;
}
这篇关于poj 3104 二分答案的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
