三分应用于最优化问题的求解。在解题时没必要给出证明，只要知道问题不满足单调性，就可以尝试用三分搜索极值点，而且三分整数很少见，因为除非能够证明这种策略是正确的(即完全符合凸函数的性质，但是通常极值点不会在整点取得，如果三分整数，那么函数也不是连续的了)，否则很可能会错误，而三分应用在小数中是最常见的，比如说三分角度，三分坐标等等。
这句话里面重点是什么呢？问题不满足单调性！极值点！
如：
但我觉得三分相比二分最精髓的是什么呢？
有了互相比较的值！
我们来想一下，二分通常是怎么写的，是不是 if （mid<答案）then { left or right=mid }
但是如果题目就叫你求这个答案呢？三分就很有用处了。
对于一组数据，如果它有极值点，我们就用三分。
具体怎么实现，就是我的当前左答案小于or大于右答案，然后 left or right=mid ，逐步逼近极值点。
我们来一道例题
https://nanti.jisuanke.com/t/43512
很明显这题是有极值点，且只有一个，不懂怎么证明的话可以像我一样，写一个暴力程序，一个一个枚举，看枚举出来的每个值要移动多少步才符合要求，然后你就发现数据是递减后递增的。
一开始我只知道二分，所以很显而易见的做不出来，贪心又不会贪，最终只能送人头。
这题三分的做法，就是三分第一个啤酒摊的坐标，然后左边右边进行比较，之后就是常规三分做法
#include <bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f typedef long long ll; int a[1000005],i,n,m; ll l,r,mid1,mid2,ans1,ans2,ans; using namespace std; ll solve(ll x) { ll ans=0; for (int i=1;i<=n;i++) { ans+=abs(a[i]-x); x+=m; } return ans; } int main() { while (~scanf("%d%d",&n,&m)) { for (i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); l=-1e12; r=1e12; ans=INF; for (i=1;i<=100;i++) { mid1=l+(r-l)/3; mid2=r-(r-l)/3; ans1=solve(mid1); ans2=solve(mid2); if (ans1>ans2) l=mid1; else r=mid2; ans=min(ans,min(ans1,ans2)); } cout<<ans<<endl; } return 0; }