HDOJ2899

一道很水的题目，硬是被我做成有毒的题目
先讲二分法
这种多次函数照理来说是不能用二分法的（因为一般来说函数不是单调的），但是这个函数的导函数在给定（0，100）区间是单调的，所以就可以以利用二分法去找导数等于零的点，也就是要找的极小值点

#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
#define flag 1e-6
double val(double x,double y)
{
	return 6 * pow(x, 7) + 8 * pow(x, 6) + 7 * pow(x, 3) + 5 * pow(x, 2) - x*y;
}
double der(double x)
{
	return 42 * pow(x, 6) + 48 * pow(x, 5) + 21 * pow(x, 2) + 10 * x;
}
int main()
{
	int t; cin >> t;
	while (t--)
	{
		double  y; cin >> y;
		double x_mid=50.0, x_min = 0.0, x_max = 100.0;
		while (abs(der(x_mid) - y) > flag)
		{
			if (der(x_mid) > y) { x_max = x_mid; x_mid = (x_max + x_min) / 2; }
			else { x_min = x_mid; x_mid = (x_min + x_max) / 2; }
		}
		printf("%.4lf\n", val(x_mid, y));
	}
}

这个三分法是真的有毒，我在网上找到的三分查找都是先分成两半，再分，也就是四分了吧，所以害我WA了两遍，有大佬和我讲解一下为什么嘛
先把三分法的原理过一遍：首先需要明确三分法的使用条件，在给定区间内要具有相同的凹凸性（我们在后面举例说明如果不具备凹凸性三分法就不成立）

#include<iostream>
using namespace std;
#include<stdio.h>
#include<math.h>
#define flag 1e-6
double Fx(double x, double y)
{
	return 6 * pow(x, 7) + 8 * pow(x, 6) + 7 * pow(x, 3) + 5 * pow(x, 2) - x*y;
}
int main()
{
	int t; cin >> t;
	while (t--)
	{
		double  y; cin >> y;
		double x_mid1 , x_min =0, x_max = 100, x_mid2;
		while ((x_max-x_min)>flag)
		{
			x_mid1 = (x_max +2*x_min) / 3;
			x_mid2 = (2*x_max +x_min) / 3;
			if (Fx(x_mid1, y) < Fx(x_mid2, y)) 
				x_max = x_mid2;  
			else x_min=x_mid1  ; 
		}
		printf("%.4lf\n", Fx(x_max,y));
	}
}