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
| class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
auto check = [&](int m) -> bool {
int sum = 0;
for(int x : nums){
sum += (x - 1) / m + 1;
if(sum > threshold){
return false;
}
}
return true;
};
//check(l)恒为false, check(r)恒为true
int l = 0, r = ranges::max(nums);
while(l + 1 < r){
int mid = l + (r - l) / 2;
if(check(mid))
r = mid;
else
l = mid;
}
return r;
}
};
|
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
| class Solution {
public:
long long minimumTime(vector<int>& time, int totalTrips) {
sort(time.begin(), time.end());
auto check = [&](long long m) -> bool {
long long sum = 0;
for(int t : time){
sum += m / t;
if(sum >= totalTrips){
return true;
}
}
return false;
};
long long l = 0, r = (long long)totalTrips * time[0];
while(l + 1 < r){
long long mid = l + (r - l) / 2;
if(check(mid)){
r = mid;
}else{
l = mid;
}
}
return r;
}
};
|
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
| class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
auto check = [&](int m){
int tmp = m, cnt = 1;
for(int w : weights){
if(tmp >= w) tmp -= w;
else{
tmp = m - w;
cnt++;
}
if(cnt > days) return false;
}
return true;
};
int maxW = -1, sum = 0;
for(int w : weights){
if(w > maxW) maxW = w;
sum += w;
}
int l = maxW - 1, r = sum;
while(l + 1 < r){
int mid = l + (r - l) / 2;
if(check(mid)){
r = mid;
}else{
l = mid;
}
}
return r;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
auto check = [&](int m) -> bool{
int sum = 0;
for(int i : piles){
sum += (i - 1) / m;
if(sum > h - piles.size()) return false;
}
return true;
};
int l = 0, r = ranges::max(piles);
while(l + 1 < r){
int mid = l + (r - l) / 2;
if(check(mid)){
r = mid;
}else{
l = mid;
}
}
return r;
}
};
|
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
| class Solution {
public:
long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
auto check = [&](long long m){
int sum = mountainHeight;
for(int t : workerTimes){
sum -= ((int) sqrt(m / t * 8 + 1) - 1) / 2;
if(sum <= 0){
return true;
}
}
return false;
};
int h = (mountainHeight - 1) / workerTimes.size() + 1; //上取整
long long l = 0, r = (long long)ranges::max(workerTimes) * h * (h + 1) / 2;
while(l + 1 < r){
long long mid = l + (r - l) / 2;
if(check(mid)){
r = mid;
}else{
l = mid;
}
}
return r;
}
};
|
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
| class Solution {
public:
int minTime(string s, vector<int>& order, int k) {
int n = s.length();
if(1LL * (1 + n) * n / 2 < (long long)k){
return -1;
}
auto check = [&](int m, string s) -> bool{
for(int i=0; i<=m; i++){
s[order[i]] = '*';
}
int cnt = 0;
int last = -1; //上一个‘*’的位置
for(int i=0; i<n; i++){
if(s[i] == '*'){
last = i;
}
cnt += last + 1;
if(cnt >= k){
return true;
}
}
return false;
};
long long l = -1, r = n - 1;
while(l + 1 < r){
long long mid = l + (r - l) / 2;
if(check(mid, s)){
r = mid;
}else{
l = mid;
}
}
return r;
}
};
|
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
| class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
auto check = [&](int m) -> bool{
int n = heaters.size();
int nn = houses.size();
int covered = 0;
for(int i=0; i<n; i++){
int l = heaters[i] - m;
int r = heaters[i] + m;
while(covered < nn && l <= houses[covered] && houses[covered] <= r){
covered++;
}
}
if(covered < nn)
return false;
else
return true;
};
int n = heaters.size();
int nn = houses.size();
int l = -1, r = max(houses[nn - 1], heaters[n - 1]);
while(l + 1 < r){
int mid = l + (r - l) / 2;
if(check(mid)){
r = mid;
}else{
l = mid;
}
}
return r;
}
};
|
8.https://leetcode.cn/problems/minimum-time-to-repair-cars/description/
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
| class Solution {
public:
long long repairCars(vector<int>& ranks, int cars) {
auto check = [&](long long m) -> bool{
long long sum = 0, n = ranks.size();
for(int i=0; i<n; i++){
sum += (int)sqrt(m / ranks[i]);
if(sum >= cars){
return true;
}
}
return false;
};
long long l = 0, r = ranges::max(ranks) * 1L * cars * cars;
while(l + 1 < r){
long long mid = l + (r - l) / 2;
if(check(mid)){
r = mid;
}else{
l = mid;
}
}
return r;
}
};
|
9.https://leetcode.cn/problems/minimum-number-of-days-to-make-m-bouquets/description/
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
| class Solution {
public:
int minDays(vector<int>& bloomDay, int m, int k) {
int n = bloomDay.size();
if((long long)n < 1L * m * k) return -1;
auto check = [&](int mid) -> bool{
int sum = 0;
for(int i=0; i<n; i++){
int l = -1, r = -1;
if(bloomDay[i] <= mid){
l = i;
while(i < n && bloomDay[i] <= mid){
i++;
}
r = i--;
}
sum += (r - l) / k;
if(sum >= m){
return true;
}
}
return false;
};
int l = 0, r = ranges::max(bloomDay);
while(l + 1 < r){
int mid = l + (r - l) / 2;
if(check(mid)){
r = mid;
}else{
l = mid;
}
}
return r;
}
};
|
10.https://leetcode.cn/problems/earliest-second-to-mark-indices-i/description/
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
| class Solution {
public:
int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
int n = nums.size(), m = changeIndices.size();
auto check = [&](int mid) -> int{
vector<bool> marked(n);
int time = mid;
for(int i=mid-1; i>=0; i--){
if(!marked[changeIndices[i] - 1]){
time -= nums[changeIndices[i] - 1] + 1;
marked[changeIndices[i] - 1] = true; //清零、标记
}
if(time < 0){
return -1;
}
time = min(time, i);
}
for(int i=0; i<n; i++){
if(!marked[i]){
return -1;
}
}
return mid;
};
if(check(m) == -1){
return -1;
}
int l = 0, r = m;
while(l + 1 < r){
int mid = l + (r - l) / 2;
if(check(mid) != -1){
r = mid;
}else{
l = mid;
}
}
return r;
}
};
|