這好像是我第一次嘗試寫一個新知識入門
而不是習題解

文章目錄

• 三分概念
• 模板
• 例題：曲線
• • 題目
  • 題解
  • 代碼實現

三分概念

我們都知道，二分是在一個單調函數（即一次函數）上通過每次查找折半的方式，對答案進行搜索查找。那么，三分就是在一個單峰函數（二次函數，拋物線）上，不斷地將答案分為三份，
通過兩者的比較來求取這個峰值（極值）的答案。
對于所要求解的范圍[L,R]，計算出兩個點M1和M2將整個范圍分為三段，
M1在從左數1/3處，M2在從左數2/3處。每次計算時，計算M1處和M2處的值，
在這兩個點中，更接近我們想要的答案的那個值稱為好點，另一個稱為壞點，
并更新靠近壞點那一側的邊界值。最后直到搜索到我們的答案為止。

也就是如果我們要找最大值，且M1>M2就三分l~M2，即把右端點r變為M2

為什么是靠近壞點呢？以求最大值為例（凸峰函數，a<0）解釋
因為我們是三分答案，有可能出現M1，M2都在我們答案點的左邊或者右邊，

假設都在右邊，M1的值大于M2的值，如果我們靠近好點，把l變成了M1，就徹底離開了答案的懷抱！！
反之，靠近壞點，更改r，在新的[l,r]區間內仍是包含著答案點的！

換言之，我們找到了兩個點，M1優于M2，那么[M2,r]也一定是不優于M1的，就可以大膽舍去
但我們不能保證[l,M1]全都不優于M1，無法割舍的愛

模板

三分是與二分相似的，count就是我們對答案正確性的判斷

int count ( int x ) { ......//進行答案處理 } void sanfen ( double l, double r ) {if ( ( r - l ) < eps ) {id = l;return;}double mid1 = l + ( r - l ) / 3.0;double mid2 = r - ( r - l ) / 3.0;if ( count ( mid1 ) < count ( mid2 ) )sanfen ( l, mid2 );elsesanfen ( mid1, r ); }

例題：曲線

題目

給定n個二次函數f1(x),f2(x),…,fn(x)（均形如ax^2+bx+c），設F(x)=max{f1(x),f2(x),…,fn(x)}，求F(x)在區間[0,1000]上的最小值。

輸入格式
輸入第一行為正整數T，表示有T 組數據。

每組數據第一行一個正整數n,接著n行，每行3個整數a,b,c ，用來表示每個二次函數的3個系數，
注意二次函數有可能退化成一次。

輸出格式
每組數據輸出一行，表示F(x)的在區間[0,1000]上的最小值。答案精確到小數點后四位，四舍五入。

輸入輸出樣例
輸入
2
1
2 0 0
2
2 0 0
2 -4 2
輸出
0.0000
0.5000
說明/提示
【數據范圍】
T < 10， n ≤ 10000,0 ≤ a ≤ 100，|b| ≤ 5000, |c| ≤ 5000 前50%數據n ≤ 100

題解

說了這道題是例題，那么肯定是三分啦！but。。。
我竟然和仙女同學們一起討論了為什么是三分

我們以題目要求來分析，用最簡單的兩個函數為例，如圖：

每次都要取最大值，也就意味著當至少兩個函數遇到相交點，
如果第一個函數開始遞增，那么就必定函數逐步遞減有一段會代替它，接上它
就根本不會出現大波浪卷發的形狀，不能理解也沒關系，好好想想就行了！這不重要

這道題就是個模板，所以沒有什么思維可講，唯一有點臭不要臉的就是，精度！！！
eps不能卡著四位小數開，
因為題目要的是y也就是函數結果的精度四位，而我們三分的是x，精度要更高開個1e-9就能卡過了
我被卡哭了，本仙女也不會告訴你我剛開始連題目都理解錯了~

代碼實現

#include <cstdio> #include <iostream> using namespace std; #define MAXN 100005 #define eps 1e-9 #define L 0 #define R 1000 int n, t; double a[MAXN], b[MAXN], c[MAXN]; double id;double count ( double x ) {double val = -2147483647;for ( int i = 1;i <= n;i ++ )val = max ( a[i] * x * x + b[i] * x + c[i], val );return val; }void sanfen ( double l, double r ) {if ( ( r - l ) < eps ) {id = l;return;}double mid1 = l + ( r - l ) / 3.0;double mid2 = r - ( r - l ) / 3.0;if ( count ( mid1 ) < count ( mid2 ) )sanfen ( l, mid2 );elsesanfen ( mid1, r ); }int main() {scanf ( "%d", &t );while ( t -- ) {scanf ( "%d", &n );for ( int i = 1;i <= n;i ++ )scanf ( "%lf %lf %lf", &a[i], &b[i], &c[i] );sanfen ( L, R );printf ( "%.4lf\n", count ( id ) );}return 0; }

好了，三分就這樣啦，感覺。。。

總結

以上是生活随笔為你收集整理的学习三分 （概念 + 模板 + 例题：曲线）的全部內容，希望文章能夠幫你解決所遇到的問題。

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