求证明这份代码倍增部分的时间复杂度
查看原帖
求证明这份代码倍增部分的时间复杂度
709949
M1rac0楼主2022/7/17 23:09
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, a[N], ans;

signed main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] += a[i - 1];
  int l = 1;
  while (l <= n) {
    int r = l, len = 1;
    while (len)
      if (r + len <= n && a[r + len] - a[l - 1] <= m) r += len, len <<= 1;
      else len >>= 1;
    l = r + 1, ans++;
  }
  printf("%d\n", ans);
  return 0;
}
2022/7/17 23:09
加载中...