求单峰区间的极值

整数三分

// 求极大值 [l,r]
int find(int l, int r) {
  int m1, m2, val = 0, ret;
  while (r - l >= 3) {
    m1 = l + (r - l) / 3;
    m2 = r - (r - l) / 3;
    if (work(m1) > work(m2))
      r = m2;
    else
      l = m1;
  }
  for (int i = l; i <= r; i++) {
    int res = work(i);
    if (val < res) val = res, ret = i;
  }
  return ret;
}

浮点三分

// 求极小值
double find(double l, double r) {
    double m1, m2;
    while (r - l >= eps) {
        m1 = l + (r - l) / 3;
        m2 = r - (r - l) / 3;
        if (work(m1) > work(m2))
            l = m1;
        else
            r = m2;
    }
    return (m1 + m2) / 2;
}
最后修改:2020 年 07 月 30 日 10 : 19 PM