---

P1883 【模板】三分 | 函数

原创 于 2024-04-29 13:57:23 发布 · 粉丝可见 · 329 阅读 · 6 · 2 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/138310161

本题链接： 【模板】三分 | 函数 - 洛谷

题目：

样例：

cobol<br/>2<br/>1<br/>2 0 0<br/>2<br/>2 0 0<br/>2 -4 2<br/>

<br/>0.0000<br/>0.5000<br/>

思路：

三分，就是将一段区间分成三等份，随后已知缩小中间的一段区间，以达到寻找极值问题。

三分，一般适用于，抛物线性质类的题目，以后遇到关于函数求值类的或者变相的函数求值类的题目，应该联想到三分。

具体的三分逻辑理解，可以参考网上的一些模拟视频： 【4K算法详解】【二分与三分】从二分法到牛顿法，领着你的思维带你观望方程求解与数值优化算法_哔哩哔哩_bilibili

代码详解如下：

#include <iostream>
#include <vector>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define INF 0x3f3f3f3f3f3f
#define umap unordered_map
#define All(x) x.begin(),x.end()
// #pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();

signed main()
{
//	freopen("a.txt", "r", stdin);
	// IOS;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}

// F(x) 式子
inline double F(int a,int b,int c,double x)
{
	return (a*x*x + b*x + c);
}
vector<vector<int>>f;	// 存储多个函数

inline double check(double x)
{
	double ans = -INF * 1.0;	// 取无穷小值，找极大值
	for(auto &now:f)	// 遍历多个函数
	{
		int a = now[0];
		int b = now[1];
		int c = now[2];
		ans = max(ans,F(a,b,c,x));
	}
	return ans;
}

inline void solve()
{
	int sz;
	cin >> sz;
	f.clear();
	while(sz--)
	{
		int a,b,c;
		cin >> a >> b >> c;
		vector<int>ftem = {a,b,c};
		f.emplace_back(ftem);
	}
	
	// 因为是求 double 浮点数，所以三分的时候应该 r - l >= 1e-13 ,
	// 以及 l 和 r 的变化应该浮点数的形式变化 和 二分板子差不多
	double l = 0.0,r = 1000.0;
	while(r - l >= 1e-13)
	{
		// 截取中间区间,这里 / 3 是分成 3 等份,r - l 是l 和 r 之间的长度。
		double midl = l + (r - l) / 3.0;
		double midr = r - (r - l) / 3.0;
		
		// 判断是否符合性质，寻找最符合性质的区间点并移动
		if(check(midl) <= check(midr)) r = midr - 1e-13;
		else l = midl + 1e-13;
	}
	
	double ans = max(check(l),check(r));
	printf("%.4lf\n",ans);
}

最后提交：