二分 & 三分

• OI Wiki: https://oi-wiki.org/basic/binary/

题目	难度
2448. 使数组相等的最小开销	中等	T3 三分
Abc279_d		三分

二分

Golang：

SearchInts

func SearchInts(a []int, x int) int { return Search(len(a), func(i int) bool { return a[i] >= x }) }  func Search(n int, f func(int) bool) int { // Define f(-1) == false and f(n) == true. // Invariant: f(i-1) == false, f(j) == true. i, j := 0, n for i < j { h := int(uint(i+j) >> 1) // avoid overflow when computing h // i ≤ h < j if !f(h) { i = h + 1 // preserves f(i-1) == false } else { j = h // preserves f(j) == true } } // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i. return i }

C++：

std::lower_bound

Java：

 private int binarySearchLeftBound(boolean[] nums) {  int left = 0;  int right = nums.length;  while (left < right) {  int mid = left + (right - left) / 2;  // 边界二分 F, F,..., F, [T, T,..., T]  // ----------------------^  if (checkMid(nums, mid)) {  right = mid;  } else {  left = mid + 1;  }  }  return left;  }

三分

 private long ternarySearch_u(int mn, int mx) {  long l = mn, r = mx;  while (r - l > 2) {  long m1 = (l * 2 + r) / 3;  long m2 = (l + r * 2) / 3;  if (f(m1) > f(m2)) {  l = m1;  } else {  r = m2;  }  }  long res = f(l);  for (long i = l + 1; i <= r; i++) {  res = Math.min(res, f(i));  }  return res;  }   private long f(long mid) {  long res = 0;  for (int i = 0; i < nums.length; i++) {  res += Math.abs(nums[i] - mid) * cost[i];  }  return res;  }

2448. 使数组相等的最小开销

import java.util.Arrays;  public class Solution2448 {  private int[] nums;  private int[] cost;   public long minCost(int[] nums, int[] cost) {  this.nums = nums;  this.cost = cost;  int min = Arrays.stream(nums).min().orElseThrow();  int max = Arrays.stream(nums).max().orElseThrow();  return ternarySearch_u(min, max);  }   private long ternarySearch_u(int mn, int mx) {  long l = mn, r = mx;  while (r - l > 2) {  long m1 = (l * 2 + r) / 3;  long m2 = (l + r * 2) / 3;  if (f(m1) > f(m2)) {  l = m1;  } else {  r = m2;  }  }  long res = f(l);  for (long i = l + 1; i <= r; i++) {  res = Math.min(res, f(i));  }  return res;  }   private long f(long mid) {  long res = 0;  for (int i = 0; i < nums.length; i++) {  res += Math.abs(nums[i] - mid) * cost[i];  }  return res;  } }

（全文完）