二分法

以下摘要由GPT-4o生成:
本文讨论了序列二分的几种方法，包括暴力解法和二分优化。首先介绍了upper_bound和lower_bound函数的使用，前者用于找到序列中第一个严格大于x的位置，后者用于找到大于等于x的位置。接着，强调了核心代码的定制修改。此外，还提到了一些相关题目，如最小值最大问题和数列分段问题，同样适用于二分法的应用，特别是在处理具有单调性和二分性的场景中。

序列二分

0最大通过数 - 蓝桥云课

• 暴力解法

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  typedef long long LL;
  //暴力解法
  const int N = 200010; //2*10^5
  int n, m, k;
  LL a[N],b[N];
  int ans;
  int main() {
      cin >> n >> m >> k;
      for (int i  = 1; i <= n; i++) {
          scanf("%lld", &a[i]);
          a[i] = a[i - 1] + a[i];
      }
      for (int j = 1; j <= m; j++) {
          scanf("%lld", &b[j]);
          b[j] = b[j - 1] + b[j];
      }
      //求前缀和数组，进入到第i关所需要的能量为a[i];
      for (int i = 0; i <= n; i++) {
          LL temp = k - a[i];
          if (temp < 0) break;
          for (int j = 0; j <= m; j++) {
              if (temp < b[j]) {//找出第一个不能打的关卡
              ans = max(i + j - 1, ans);
              break;
              }
          }
      }
      cout << ans;
  
  
      return 0;
  }

• 二分优化

• upper_bound(a.begin(), a.end(), x) - a找出序列中第一个严格大于x的位置(与sort都为左闭右开区间)

• *lower_bound 找出序列中大于等于x的位置,返回值为引用。

• 手写上述两个序列二分

  int l = 0; r = a.size() - 1;
  while (l < r) {
  	int mid = l + r + 1 >> 1;
  	if (a[mid] <= x) l = mid;
  	else r = mid - 1;
  }
  cout << l << "为大于x的位置,即upper_bound"

  int l = 0; r = a.size() - 1;
  while (l < r) {
  	int mid = l + r >> 1;
  	if (a[mid] >= x) r = mid;
  	else l = mid + 1;
  }
  cout << l << "为大于等于x的位置,即lower_bound"

  **对于核心代码的修改 **

for (int i = 0; i <= n; i++) {
       LL temp = k - a[i];
       if (temp < 0) break;
       int j = upper_bound(b, b + m + 1, temp) - b - 1;
       ans = max(ans, j + i);
   }

答案二分

二分答案 - 题目详情 - HydroOJ最小值最大

• 暴力解法

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  typedef long long LL;
  //暴力解法
  const int N = 100010; //1*10^5
  int n, k;
  int a[N];
  int main() {
      scanf("%d %d", &n, &k);
      for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  
      for (int i = 1; i <= 1e14; i++) {//依次枚举这个最小值,ER
          LL x = k;//k次操作，随着i枚举值的最大，x成递减趋势。
          for (int j = 1; j <= n; j++) {
              if (a[j] < i) {//如果当前值有小于这个最小值的，那么可以进行增大这个数，进行操作，直到操作数小于0
                  x = x - (i - a[j]);//需要这个最小值i最大,x最小
              }
              if(x < 0) {
                  cout << i - 1;
                  break;
              } //减小到为0的时候，
          }
      }
      return 0;
  }

• 核心代码二分优化

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  typedef long long LL;
  //暴力解法
  const int N = 100010; //1*10^5
  LL n, k;
  int a[N];
  bool check(LL m) {
      LL x = k;//k次操作，随着i枚举值的最大，x成递减趋势。
      for (int j = 1; j <= n; j++) {
          if (a[j] < m) {
              x = x - (m - a[j]);//需要这个最小值i最大,x最小 
          }
          if(x < 0) {
              return false;
          } //减小到为0的时候，
      }
      return true;
  }
  int main() {
      scanf("%lld %lld", &n, &k);
      for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  
      LL l = 1, r = 1e14;
      while (l < r) {
          LL mid = l + r + 1>> 1;
          if (check(mid)) l = mid;
          else r = mid - 1;
      }
  cout << l;
      return 0;
  }

• 最大值最小

P1182 数列分段 Section II - 洛谷

• 暴力代码

  for (int i = 1; i <= R; i++) {
      //R即为最大值的最大范围
      //即分一个段的时候，这个段的最大值,N个数，每个数为10^8,即N * 10^8
  	 int sum = 0, cnt = 1;
      for (int j = 1; j <= n; j++) {
          if (a[j] > mid) return;//终止条件。
          if (sum + a[j] <= mid) {
              sum += a[j];
          } else {
              sum = a[j];
              cnt ++;
          }
      }
  }

• 二分优化

  #include <iostream>
  #include <cstdio>
  using namespace std;
  int n, m;
  const int N = 1e5 + 10;
  int a[N];
  bool check(int mid) {
      int sum = 0, cnt = 1;
      for (int j = 1; j <= n; j++) {
          if (a[j] > mid) return false;
          if (sum + a[j] <= mid) {
              sum += a[j];
          } else {
              sum = a[j];
              cnt ++;
          }
      }
      return cnt <= m;//m是固定的段数，cnt是当前答案分的段数，说明分的ans太大，固定段数用不完
  }
  
  int main() {
      cin >> n >> m;
      for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  
      int l = 0, r = 1e9;
      while (l < r) {
          int mid = l + r >> 1;
          if (check(mid)) {//如果当前值可以就缩小ans
              r = mid;
          }else l = mid + 1;
      }
      cout << l;
      return 0;
  }

浮点数二分

• 注意精度损失，一般相差100倍即可。

#include <iostream>
#include <cstdio>
using namespace std;
double esp = 1e-9;
int N, M;

bool check(double x) {
  double ans = 1;
  for(int i = 0; i < M; i++) {
    ans = ans * x;
  }
  return ans <= N;//乘出来结果小于N，即代表l = mid ,还可以继续增大
}

int main()
{
  cin >> N >> M;
  double l = 1, r = N;//最多为M为1的时候，r即N；
  while (l + esp < r) {
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
  }  
  printf("%0.7f", l);

  return 0;
}

• 具有二分性，单调性