https://www.luogu.org/problemnew/show/P3382
二分用于单调函数, 三分用于凹凸函数.
三分就是把区间分成三份, 设左右端点为L和R, 有两种分法。
第一种是区间内的第一个点lmid = (L + R) / 2, 第二个点rmid = (lmid + R) / 2。
第二种是lmid = l + (r – l) / 3, rmid = l + 2 * (r – l) / 3。
然后判断函数在这两个位置的值，根据实际情况缩小答案的区间。
比如求凸函数最大值，如果f(lmid) < f(rmid), 则L = lmid，否则R = rmid。 然后循环一定次数保证精度，最后的R就是最大值点。 如果是整数三分，那就是L = lmid + 1，否则R = rmid - 1。 注意1e-5的精度至少64次，1e-6建议100次。 实数三分：
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e3 + 5, mod = 1e9 + 7;int n;double a[15];double F(double x){ double sum = 0; for (int i = 0; i <= n; ++i){ double prod = 1; for (int j = 0; j < i; ++j){ prod = prod * x; } sum += a[i] * prod; } return sum;}int main(){ ios::sync_with_stdio(0); cin.tie(0); double l, r; cin >> n >> l >> r; for (int i = n; i >= 0; --i) cin >> a[i]; for (int i = 0; i < 32; ++i){ //注意观察区别 double lmid = l + (r - l) / 3, rmid = l + 2 * (r - l) / 3; //double lmid = (l + r) / 2, rmid = (lmid + r) / 2; if (F(lmid) < F(rmid)) l = lmid; else r = rmid; } cout << fixed << setprecision(5) << r << endl; return 0;}
整数三分：
这里有个小技巧，为什么要r – l > 3呢，是为了防止l和r离的太近使得l或r直接跳过了极值点，二分不会出现这样的问题，最后求出来的[l, r]是一个区间，极值点一定在这个区间里，挨个暴力就好了，可以根据不同的题适当改变区间大小，这样check函数不需要那么严格。
int l = mi, r = ma;while (r - l > 3){ int t = (r - l) / 3; int lmid = l + t, rmid = l + 2 * t; if (check(lmid, rmid)) l = lmid + 1; else r = rmid - 1;}