ARC 100 C - Linear Approximation题解---三分法 _Linear

一卷旌收千骑虏，万全身出百重围。这篇文章主要讲述ARC 100 C - Linear Approximation题解---三分法相关的知识，希望能为你提供帮助。

题目链接：
https://arc100.contest.atcoder.jp/tasks/arc100_a
分析：
【ARC 100 C - Linear Approximation题解---三分法】比赛时做这题想到一个瞎搞的方法就是在平均数上下波动一下取最小值，然后大佬yjw学长说这就是个严格单调单峰函数直接三分法就好了,虽然之前就听过则还是第一次打
三分法
设有最大值函数f(x)定义域为([l,r])，我们在定义域内找两个点(lmid,rmid(lmid< rmid))
- 若(f(lmid)< f(rmid)),要么(lmid)和(rmid)都在单峰左边，要么(lmid)在左边,(rmid)在右边,但无论怎样(lmid)都在单峰左边,于是将(l=lmid)
- 若(f(lmid)< f(rmid)),分析相似,将(r=rmid)
- 若(f(lmid)==f(rmid))emmm这个其实我也不知道怎么处理，随便按上面一种情况来吧但总感觉不太稳
代码:

#include < iostream> #include < cstdio> #include < cstdlib> #include < cstring> #include < cctype> #include < map> #include < queue> #include < algorithm> #define ri register int #define ll long long using namespace std; const int maxn=200005; const int inf=0x7fffffff; template < class T> inline void read(T & x){ x=0; int ne=0; char c; while(!isdigit(c=getchar()))ne=c==‘-‘; x=c-48; while(isdigit(c=getchar()))x=(x< < 3)+(x< < 1)+c-48; x=ne?-x:x; return ; } int n; ll a[maxn]; ll sum=0; inline ll solve(int k){ ll cnt=0; for(ri i=1; i< =n; i++)cnt+=abs(a[i]-k); return cnt; } int main(){ read(n); for(ri i=1; i< =n; i++){ read(a[i]); a[i]=a[i]-i; } ll ans,lmid,rmid; ll l=-1e9,r=1e9; while(l< r-1){ lmid=(l+r)> > 1,rmid=(lmid+r)> > 1; if(solve(lmid)> solve(rmid))l=lmid; else r=rmid; } if(solve(l)< solve(r))ans=l; else ans=r; printf("%lld ",solve(ans)); return 0; }