Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 500500 points
Problem Statement
We have NN logs of lengths A1,A2,?ANA1,A2,?AN.
We can cut these logs at most KK times in total. When a log of length LL is cut at a point whose distance from an end of the log is tt (0<t<L)(0<t<L), it becomes two logs of lengths tt and L?tL?t.
Find the shortest possible length of the longest log after at most KK cuts, and print it after rounding up to an integer.
Constraints
- 1≤N≤2×1051≤N≤2×105
- 0≤K≤1090≤K≤109
- 1≤Ai≤1091≤Ai≤109
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
NN KK A1A1 A2A2 ?? ANAN
Output
Print an integer representing the answer.
Sample Input 1 Copy
Copy
2 3 7 9
Sample Output 1 Copy
Copy
4
- First, we will cut the log of length 77 at a point whose distance from an end of the log is 3.53.5, resulting in two logs of length 3.53.5 each.
- Next, we will cut the log of length 99 at a point whose distance from an end of the log is 33, resulting in two logs of length 33 and 66.
- Lastly, we will cut the log of length 66 at a point whose distance from an end of the log is 3.33.3, resulting in two logs of length 3.33.3 and 2.72.7.
In this case, the longest length of a log will be 3.53.5, which is the shortest possible result. After rounding up to an integer, the output should be 44.
Sample Input 2 Copy
Copy
3 0 3 4 5
Sample Output 2 Copy
Copy
5
Sample Input 3 Copy
Copy
10 10 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202
Sample Output 3 Copy
Copy
292638192
#include<iostream>
#include<cmath>
#define ll long longusing namespace std;int n,k;
double num[200010];
double eps = 1e-6;int can(double len)
{ll rul = 0;for(int i=0; i<n; i++){ll t = num[i] / len;if(fabs(num[i] - t * len) > eps) t++;rul+=t-1;if(rul > k) return 0;} return 1;
}int main()
{cin>>n>>k;for(int i=0; i<n; i++) cin>>num[i];double l = 1e-9, r = 1e9, mid;while(l < r - eps){mid = (l + r) / 2;if(can(mid)) r = mid;else l = mid;}printf("%.0lf",ceil(r));return 0;
}