二分答案
假设当前二分的答案为 t，那么：
对于ai <= t的衣服，显然让它们自然风干就可以了。
对于ai > t的衣服，我们需要知道该衣服最少用多少次烘干机。
设该衣服用了x1分钟风干，用了x2分钟烘干机。
那么有 x1 + x2 = t 和 ai <= x1 + x2 * k，联立两式可得 x2 >= (ai - t) / (k - 1)，即最少使用次数为[(ai - t) / (k - 1)] 的最小上界。
最后，判断一下总使用次数是否少于 t 即可。
记得不要除零
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define maxn 100050
typedef long long ll;
ll k,num[maxn],ans;
int n;
bool check(ll mid){
ll cnt = 0;
for (int i = 0; i < n; i ++){
if (num[i] <= mid) continue;
cnt += (num[i] - mid + k - 2)/(k - 1);
if (cnt > mid) return false;
}
return true;
}
ll solve(){
ll l = 1,mid, r = ans;
while (l <= r){
mid = MID(l,r);
if (check(mid)) {
r = mid - 1;
ans = mid;
}else l = mid + 1;
}
return ans;
}
int main(){
scanf("%d", &n);
ans = 0;
for (int i = 0; i < n; i ++){
scanf("%lld", &num[i]);
ans = max(num[i],ans);
}
scanf("%lld", &k);
printf("%lldn",k == 1?ans : solve());
return 0;
}
|