classSolution { public: longlongcountFairPairs(vector<int>& nums, int lower, int upper){ longlong ans = 0; sort(nums.begin(), nums.end()); int n = nums.size(); for (int i = 0; i < n; i ++) { int left = -1, right = n; int temp_lower = lower - nums[i]; int temp_upper = upper - nums[i]; int nearupper = 0, nearlower = 0; // r 表示第一个 >= lower while(left + 1 != right) { int mid = left + (right - left) / 2; if (nums[mid] >= temp_lower) right = mid; else left = mid; } if (right == n) continue; else nearlower = right; left = -1, right = n; while(left + 1 != right) { int mid = left + (right - left) / 2; if (nums[mid] <= temp_upper) left = mid; else right = mid; } if (left == -1) continue; else nearupper = left; if (i >= nearlower && i <= nearupper) ans += nearupper - nearlower; else ans += nearupper - nearlower + 1; } return ans / 2; } };
classSolution { public: boolcheck(vector<int>& piles, longlong mid, int h){ longlong sum = 0; for (int i = 0; i < piles.size(); i ++) { if (piles[i] % mid == 0) sum += piles[i] / mid; else sum += piles[i] / mid + 1; } return sum <= h; } intminEatingSpeed(vector<int>& piles, int h){ longlong sum = 0; int n = piles.size(); for (int i = 0; i < n; i ++) { sum += piles[i]; } longlong left = 0, right = sum + 1; while(left + 1 != right) { longlong mid = left + (right - left) / 2; if (check(piles, mid, h)) right = mid; else left = mid; } return right; } };
classSolution { public: boolcheck(vector<int>& time, longlong mid, int totalTrips){ int sum = 0; for (int i = 0; i < time.size(); i ++) { if ((mid / time[i])) { sum += mid / time[i]; if (sum >= totalTrips) returntrue; } elsebreak; } returnfalse; }
longlongminimumTime(vector<int>& time, int totalTrips){ sort(time.begin(), time.end()); longlong left = time[0] - 1; longlong right = (longlong) time[0] * totalTrips + 1; while(left + 1 != right) { longlong mid = left + (right - left) / 2; if (check(time, mid, totalTrips)) right = mid; else left = mid; } return right; } };
classSolution { public: boolcheck(vector<int>& nums, int mid){ longlong extra = 0; for (int i = nums.size() - 1; i > 0; i --) { if (nums[i] + extra > mid) { extra = (longlong)nums[i] + extra - mid; } else extra = 0; } return nums[0] + extra <= mid; } intminimizeArrayValue(vector<int>& nums){ int left = -1, right = ranges::max(nums) + 1; while (left + 1 != right) { int mid = left + (right - left) / 2; if (check(nums, mid)) right = mid; else left = mid; } return right; } };
classSolution { public: // 给定 price 和 任意两者的差 mid,求出最多的k intcheck(vector<int>& price, int mid){ int ans = 1, pre = price[0]; for (int p : price) { if (p >= pre + mid) { ans ++; pre = p; } } return ans; } intmaximumTastiness(vector<int>& price, int k){ sort(price.begin(), price.end()); int n = price.size(); int left = 0, right = (price[n - 1] - price[0]) / (k - 1) + 1; while (left + 1 != right) { int mid = left + (right - left) / 2; if (check(price, mid) >= k) left = mid; else right = mid; } return left; } };