• 題目鏈接：

  https://arc100.contest.atcoder.jp/tasks/arc100_a

• 分析：

  比賽時做這題想到一個瞎搞的方法就是在平均數上下波動一下取最小值，然后大佬yjw學長說這就是個嚴格單調單峰函數直接三分法就好了,雖然之前就聽過則還是第一次打

• 三分法

  設有最大值函數f(x)定義域為\([l,r]\)，我們在定義域內找兩個點\(lmid,rmid(lmid<rmid)\)

  • 若\(f(lmid)<f(rmid)\),要么\(lmid\)和\(rmid\)都在單峰左邊，要么\(lmid\)在左邊,\(rmid\)在右邊,但無論怎樣\(lmid\)都在單峰左邊,于是將\(l=lmid\)

  • 若\(f(rmid)<f(lmid)\),分析相似,將\(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\n",solve(ans));return 0; }

轉載于:https://www.cnblogs.com/Rye-Catcher/p/9255304.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的ARC 100 C - Linear Approximation题解---三分法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。