生活随笔
收集整理的這篇文章主要介紹了
POJ 3104 Drying【二分搜索】最大化最小值问题
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
?題意
有N件衣服，每件衣服的函數量為ai，每分鐘可以自然脫水1單位；有一個脫水機，每次只能用于一件衣服，每分鐘脫水K單位，脫水時，不自然風干，求所有衣服全部脫水的最短時間
分析
二分查找最短時間，下界為1，上界為N件衣服中最大含水量，全部脫水的最小時間mid
對于每一件衣服，若ai小于等于mid，則讓其自然風干若ai大于mid，則采用脫水機[X1]分鐘+自然風干[X2]分鐘的方法，那么mid=X1+X2，ai<=x1*k+x2，即x1>=(ai-mid)/(k-1)(ai-mid)/(k-1)向上取整就是這件衣服脫水的最短時間
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#include<cstdio>
#include<string>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#define mod 998244353
#define INF 0x3f3f3f3f
#define eps 1e-6
using namespace std;
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
ll a[maxn];
ll k;
int n;
bool check(ll mid){ll sum=0;for(int i=1;i<=n;i++){if(a[i]>mid)sum+=(ll)ceil(1.0*(a[i]-mid)/(k-1));}return sum>mid;
}
int main(){while(scanf("%d",&n)!=EOF){ll MAX=-1;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);MAX=max(MAX,a[i]);}scanf("%lld",&k);if(k==1){printf("%lld\n",MAX);continue;}ll right=MAX,left=1;while(left<=right){ll mid=(left+right)>>1;if(check(mid))left=mid+1;elseright=mid-1;}printf("%lld\n",left);}return 0;
}
/*
3
2 3 9
5
3
2 3 6
5
*/
?
總結
以上是生活随笔為你收集整理的POJ 3104 Drying【二分搜索】最大化最小值问题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
