难度增加的抽签问题

http://book.2cto.com/201306/25153.html
一堆数字中, 是否存在a+b+c+d=m? 数字可以重复.

O(n²logn)的算法
但是，将n=1000带入n³logn，会发现这依然是远远不够的，必须要对算法做进一步优化。刚才我们只着眼于四重循环程序中最内层的循环。接下来，让我们着眼于内侧的两个循环。
同刚才一样的思路，内侧的两个循环是在
检查是否有c和d使得Kc+Kd=m-Ka-Kb
这种情况并不能直接使用二分搜索。但是，如果预先枚举出k_c+k_d所得的n²个数字并排好序，便可以利用二分搜索了。
该算法
n   排序O(n²logn)时间
n   循环O(n²logn)时间
总的也是O(n²logn)时间。这样就可以确信即便n=1000也能妥善应对了。

int n, m, k[MAX_N];
// 保存2个数的和的数列
int kk[MAX_N * MAX_N];

bool binary_search(int x) {
  // x的存在范围是kk[l], kk[l+1], …, kk[r-1].
  int l = 0, r = n * n;
  // 反复操作直到存在范围为空
  while (r - l >= 1) {
    int i = (l + r) / 2;
    if (kk[i] == x) return true; // 找到x
    else if (kk[i] < x) l = i + 1;
    else r = i;
  }
  // 没找到x
  return false;
}
void solve() {
  // 枚举k[c]+k[d]的和
  for (int c = 0; c < n; c++) {

    for (int d = 0; d < n; d++) {
      kk[c * n + d] = k[c] + k[d];
    }
  }
  // 排序以便进行二分搜索
  sort(kk, kk + n * n);
  bool f = false;
  for (int a = 0; a < n; a++) {
    for (int b = 0; b < n; b++) {
      // 将内侧的两个循环替换成二分搜索
      if (binary_search(m - k[a] - k[b])) {
        f = true;
      }
    }
  }
  if (f) puts("Yes");
  else puts("No");

}

本问题既需要二分搜索这一基础算法知识，也需要将四个数分成两两考虑的想象力。此外，像这样从复杂度较高的算法出发，不断降低复杂度直到满足问题要求的过程，也是设计算法时常会经历的一个过程。