晾衣服
// 考虑被除数为0的情况
// 向上取整:(a+b-1)/b或ceil()
#include <bits/stdc++.h>
using namespace std;
// int clothes[50005];
vector<int> clothes(500005);
int n, m;
// 考虑被除数为0的情况
// 向上取整:(a+b-1)/b或ceil()
// 已知烘干器功率, 求最小时间
// 已知时间, 能不能求最小烘干器功率?
// 如果时间不够呢?
// 全减去时间, 剩下的个数等于时间, 有解, 解为此时最大+1
// 小于时有解, t = 3 3 6 9 3 6 99999 9999 9999 9999
// 已知烘干器功率, 已知时间, 查看是否能晾干
// bool check(vector<int> num, int time)//模拟
// {//tlogn
// for(int i = 0; i<n; i++)
// {
// num[i]-=time;
// }
// if(num[n-1]<=0) return true;
// while(time--)
// {
// num[n-1]-=m-1;
// sort(num.begin(), num.begin()+n);
// if(num[n-1]<=0) return true;
// }
// return false;
// }
bool check(int time)
{
int drytime = 0; // 比较烘干次数
if (m == 1)
{
for (int i = 0; i < n; i++)
if (clothes[i] > time)
return false;
return true;
}
for (int i = 0; i < n; i++)
{
if (clothes[i] > time)
{
// drytime+=(clothes[i]-time)%(m-1)?(clothes[i]-time)/(m-1)+1:(clothes[i]-time)/(m-1);
drytime += (clothes[i] - time + m - 2) / (m - 1); // 考虑m==1的情况
if (drytime > time)
return false;
}
}
return true;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> clothes[i];
}
cin >> m;
sort(clothes.begin(), clothes.begin() + n);
// clothes[n-1]%m==0:1-(clothes[n-1]/m)*n
// clothes[n-1]%m:1-(clothes[n-1]/m+1)*n
// 大于等于边界值
int i = 1, mid; // time最大取到多少
int j = clothes[n - 1] % m ? (clothes[n - 1] / m + 1) * n : (clothes[n - 1] / m) * n;
while (i < j)
{
mid = (i + j) / 2;
if (check(mid))
{
j = mid;
}
else
{
i = mid + 1;
}
}
cout << i;
return 0;
}