题目大意:主人公有一个烘干机,但是一次只能烘干一件衣服,每分钟失水k个单位的水量,自然烘干每分钟失水1个单位的水量(在烘干机不算自然烘干的那一个单位的水量),问你最少需要多长时间烘干衣服?
简单来说题目就是要:时间允许的情况下让时间最小,时间可以无限大,这题就是“最小化最大值”,二分法
#include <iostream>
#include <functional>
#include <algorithm> using namespace std; static int clothes[]; void Search(const int, const int);
bool judge(const long long, const int, const int);
int fcmop(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
} int main(void)//在时间允许的情况下让值最小(最小化最大值)
{
int sum_clothes, re; while (~scanf("%d", &sum_clothes))
{
for (int i = ; i < sum_clothes; i++)
scanf("%d", &clothes[i]);
scanf("%d", &re);
qsort(clothes, sum_clothes, sizeof(int), fcmop);
if (re == )
printf("%d\n", clothes[sum_clothes - ]);//注意一定不要出现0的情况
else
Search(sum_clothes, re);
}
return ;
} void Search(const int sum_clothes, const int re)
{
long long lb = , rb = (long long)10e+ + , mid; while (rb - lb > )
{
mid = (rb + lb) / ;
if (judge(mid, sum_clothes, re)) rb = mid;
else lb = mid;
}
printf("%lld\n", rb);
} bool judge(const long long times, const int sum_clothes, const int re)
{
long long use_time_now, use_sum = ;
int i; for (i = ; i < sum_clothes && clothes[i] <= times; i++); for (; i < sum_clothes; i++)
{
use_time_now = (clothes[i] - times + re - - ) / (re - );//向上取整,要先-1
use_sum += use_time_now;
if (use_sum > times)
return false;
}
return true;
}