倍增算法 | Sprooc

所谓“倍增”，就是成倍增长。在一些求解空间较大的问题中，如果使用通常的线性递推，需要线性的时间复杂度。而如果采用倍增的方式，通常能优化为对数时间复杂度。简单地解释倍增思想，就是每次都试图使结果范围扩大一定长度，如果扩大后仍满足要求，则扩大，并将下一次试图扩大的长度变为原来的两倍；若不满足，则将扩大长度减半，再次尝试，若仍不满足，则继续减半。最终，扩大长度减为0，就得到了所需的结果。下面是两个使用倍增算法的例子。

求小于T的最大数组前缀和

给定一个长度为N的数列 A，然后进行若干次询问，每次给定一个整数T,求大的 k，满足 $\sum_{i=1}^{N}{A[i]}\le T$。你的算法必须是在线的（必须即时回答每一个询问能等待收到所有询问后再统一处理），假设$0\le T\le\sum_{i=1}^{N}{A[i]}$。

最朴素的做法当然是从前往后累加数组，直到累加和大于T，时间复杂度是O(N)。
首先用O(N)的时间预处理，求出前缀和数组，再用二分查找确定小于等于T的上界。每次查找O(logN)。
如果每次查找的T都很小，使用二分查找可能还不如直接从头遍历数组，那么可以使用倍增算法：
1. 令p=1，k=0，sum=0。
2. 比较“A数组中 k之后的p个数的和”与T的关系，也就是说，如果 sum+S[k+p]-S[k]≤T,则令 sum+=S[k+p]-S[k],k+=p,p*=2,即累加上这 p个数的和，然后把p的跨度增长一倍。如果sum+S[k+p]-S[k]>T，则令 p/= 2。
3. 重复上一步，直到p的值变为0，此时k就是答案。

下面给出使用二分查找和倍增算法的代码，并比较二者的求解时间。

#include <time.h>
#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
using namespace std;

class Solution {
 private:
  vector<int> nums;
  vector<int> pre_sum;

 public:
  void set(vector<int>& xs) {
    int sum = 0;
    pre_sum.push_back(0);
    for (int x : xs) {
      sum += x;
      pre_sum.push_back(sum);
      nums.push_back(x);
    }
  }
  // 使用倍增算法查询
  int query_double(int t) {
    int sum = 0, l = 1, k = 0;
    while (l > 0) {
      if (k + l < pre_sum.size() && sum + pre_sum[k + l] - pre_sum[k] <= t) {
        sum += (pre_sum[k + l] - pre_sum[k]);
        l *= 2;
        k += l;
      } else {
        l /= 2;
      }
    }
    return k - 1;
  }
   // 通过二分查找查询
  int query_binary_search(int t) {
    auto loc = upper_bound(pre_sum.begin(), pre_sum.end(), t);
    return loc - pre_sum.begin() - 2;
  }
};

int main() {
  Solution s;
  vector<int> nums;
  // 设置随机数
  random_device rd;
  default_random_engine eng(rd());
  uniform_int_distribution<int> distr(0, 1000);

  // 生成一个随机数组
  for (int i = 0; i < 100000; i++) {
    nums.push_back(distr(eng));
  }
  s.set(nums);

  // 1.t随机分布
  // 生成测试数组
  vector<int> test_list;
  int sum = accumulate(nums.begin(), nums.end(), 0);
  distr = uniform_int_distribution<int>(0, sum);
  for (int i = 0; i < 100000; i++) {
    test_list.push_back(distr(eng));
  }

  // 用两种方法分别测试
  clock_t start, end;
  start = clock();
  for (int t : test_list) {
    s.query_binary_search(t);
  }
  end = clock();
  cout << "time of using binary search: "
       << double(end - start) / CLOCKS_PER_SEC << endl;
  start = clock();
  for (int t : test_list) {
    s.query_double(t);
  }
  end = clock();
  cout << "time of using times increase: "
       << double(end - start) / CLOCKS_PER_SEC << endl;

  // 2. t比较小
  // 生成测试数组
  test_list.clear();
  distr = uniform_int_distribution<int>(0, sum / 10000);
  for (int i = 0; i < 100000; i++) {
    test_list.push_back(distr(eng));
  }

  // 用两种方法分别测试
  start = clock();
  for (int t : test_list) {
    s.query_binary_search(t);
  }
  end = clock();
  cout << "time of using binary search: "
       << double(end - start) / CLOCKS_PER_SEC << endl;
  start = clock();
  for (int t : test_list) {
    s.query_double(t);
  }
  end = clock();
  cout << "time of using times increase: "
       << double(end - start) / CLOCKS_PER_SEC << endl;
}

下面是测试结果

// t随机分布
time of using binary search: 0.019
time of using times increase: 0.02
// t值比较小
time of using binary search: 0.011
time of using times increase: 0.006

由此可见，一般情况下，二分方法和倍增的时间复杂度接近；t比较小的情况小，倍增方法要优于二分查找。

Genius ACM

原题

给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下:

从集合 S 中取出 M 对数（即 2*M 个数，不能重复使用集合中的数，如果 S 中的整数不够 M对，则取到不能取为止），使得“每对数的差的平方”之和最大，这个最大值就称为集合 S 的“校验值”。

现在给定一个长度为 N 的数列 A 以及一个整数 T。

我们要把 A 分成若干段，使得每一段的“校验值”都不超过 T。

求最少需要分成几段。

输入格式
第一行输入整数 K，代表有 K 组测试数据。

对于每组测试数据，第一行包含三个整数 N,M,T。

第二行包含 N 个整数，表示数列A1,A2…AN。

输出格式
对于每组测试数据，输出其答案，每个答案占一行。

数据范围
1≤K≤12,
1≤N,M≤500000,
0≤T≤10^18,
0≤Ai≤2^20

输入样例：
1
2
3
4
5
2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9
输出样例：
1
2
2
1

首先，我们需要一个结论：求集合S的检验值，就是将S排序，每次取最大值和最小值构成一对，这样求出来的“每对数的差的平方和”最大。可以用只有四个数的情况证明：

$\begin{aligned} 假&设A<B<C<D，\\ &[(D-A)^2+(C-B)^2]-[(D-B)^2+(C-A)^2]\\ =&-2AD-2BC+2BD+2AC\\ =&2B(D-C)-2A(D-C)\\ =&2(B-A)(D-C) >0\\ 故&(D-A)^2+(C-B)^2>(D-B)^2+(C-A)^2 \end{aligned}$

更多数也是类似的，就不证明了。因此，可以用贪心，让每一段尽量长，就能得到最少得分段数了。于是，我们要解决的问题变为，确定左端点L之后，求最大的右端点R，使得A[l]~A[r]的校验值不超过t。当然可以使用二分思想，每次取一个可能范围的中间点mid，对A[l]~A[mid]排序，然后求校验值，与t比较后缩小范围。然而，与第一个例子类似，右端点r应该在比较靠近左端点l的位置，使用倍增可能要优于二分。故可以采用与上例类似的算法：

初始化 p = 1，R = L；
求出 [L, R + p] 这一段区间的“校验值”,若“校验值” ≤ T，则 R += p,p *= 2，否则 p /= 2；
重复上一步，直到 p 的值变为0，此时 R 即为所求。

下面是代码，其中有一个优化：每次求校验值不需要对整个数组排序，只需要对新增部分长度排序，然后与前面已排序部分合并即可。这样数组的每一段都只经过一次排序，时间复杂度为O(N*logN)。

#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <iostream>
#define LL long long
using namespace std;
int A[500000];
int B[500000];
int C[500000];

void merge(int begin, int mid, int end) {
  int l = begin, r = mid, pt = begin;
  while (l < mid && r < end) {
    if (B[l] < B[r]) {
      C[pt++] = B[l++];
    } else {
      C[pt++] = B[r++];
    }
  }
  while (l < mid) {
    C[pt++] = B[l++];
  }
  while (r < end) {
    C[pt++] = B[r++];
  }
}
// 将数组B[mid, end)排序，后将B[begin, mid)与B[mid, end)归并
void single_sort(int begin, int mid, int end) {
  sort(B + mid, B + end);
  merge(begin, mid, end);
}
// 计算排好序后的数组C在[begin, end)范围的校验值
LL cal(int begin, int end, int m) {
  int l = begin, r = end - 1;
  LL ret = 0;
  while (l < r && m > 0) {
    ret += ((LL)C[r] - C[l]) * ((LL)C[r] - C[l]);
    m--, l++, r--;
  }
  return ret;
}
int forward(int n, int begin, int m, LL t) {
  int l = 1, p = begin;
  LL sum = 0;
  while (l > 0) {
    if (p + l <= n) {
      for (int i = p; i < p + l; i++) B[i] = A[i];
      single_sort(begin, p, p + l);
      sum = cal(begin, p + l, m);
      if (sum <= t) {
        p += l;
        l *= 2;
        for (int i = begin; i < p; i++) B[i] = C[i];
      } else {
        l /= 2;
      }
    } else {
      l /= 2;
    }
  }
  if (sum == 0) p = n;
  return p;
}
int partition(int n, int m, LL t) {
  int p = 0, ret = 0;
  while (p < n) {
    p = forward(n, p, m, t);
    ret++;
  }
  return ret;
}
int main() {
  int k;
  scanf("%d", &k);
  for (int i = 0; i < k; i++) {
    int n, m;
    LL t;
    scanf("%d %d %lld", &n, &m, &t);
    for (int i = 0; i < n; i++) {
      scanf("%d", &A[i]);
    }
    printf("%d\n", partition(n, m, t));
  }
}