注意右边界 r 不满足条件, 左边界 l 满足条件
故需要使 l 尽可能大
最终情况 l 和 r 相邻，则 l 就是答案
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, k;
ll L[N];
bool check(ll x) {
ll tot = 0;
for(int i = 1; i <= n; i++) {
tot += L[i] / x;
}
return tot >= k;
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i++) {
scanf("%lld", &L[i]);
}
ll l = 0, r = N*1000;
while(l+1 < r) {
ll mid = l + r >> 1;
if(check(mid)) {
l = mid;
} else r = mid;
}
printf("%lld\n", l);
return 0;
}
|
