基础算法题——炎炎消防队（取巧、三分）

炎炎夏日

题目描述
夏天的重庆格外地炎热，很容易起火。消防士们都全副武装，一旦发生险情就立马赶往救火。森罗是消防队中的一员，他在灭火的过程中突发奇想，如果能用退火的原理求解函数求最小值，那不就可以很容易计算了吗？
翌日，森罗来到即将高考的弟弟家辅导功课，其中一道题目是这样的函数
F(x) = F(x) = 7 * x⁷ + 6 * x⁶ + 2 * x³ + 8 * x² - y * x​

给定任意一个实数y，让你求出函数的最小值。森罗回想起昨天的突发奇想，很快就给出了这个题目的解。那么，你知道他是怎么解决的吗？

输入描述:
多组输入
第一行输入测试的样例数量T
以后每一行输入实数y的值。（0 < y < 1e10）
输出描述:
每一行输出函数的最小值(精确到小数点后四位)。

示例1
输入
2
10
20
输出
-2.6256
-8.2788

备注:
x为正实数(0<x<=100)

这道题有两种解法：三分及取巧

三分法

一道解方程，很直接联想到二分法，但这道题单调性不确定，直接二分肯定是会出问题的，那该如何解决呢？
用三分确定部分区间单调性。

①、通过 F(x) = 7 * x⁷ + 6 * x⁶ + 2 * x³ + 8 * x² - y * x​，预计可以判断 F(x) 在 (0, 100] 的区间内，F(x) 应该是先递减后递增的。
我们可以通过比较 F((r+l)/2) 以及 F((r+mid)/2) 大小，找到在 x∈[mid， midd] 时，F(x) 的单调性。

大概模拟图

实现代码

#include<bits/stdc++.h>
using namespace std;
double y;
double js(double x){
	return 7*pow(x, 7)+6*pow(x, 6)
		+2*pow(x, 3)+8*pow(x, 2)-y*x;
}

int main(){
	int t;
//	freopen("data.txt", "r", stdin);
	scanf("%d", &t);
	while(t--){
		scanf("%lf", &y);
		double l=0.0001, r=100.0000;
		while(r-l >= 0.00001){
			double mid = (l+r)/2;
			double mmid = (mid+r)/2;
			if(js(mid) <= js(mmid))	//递增
				r = mmid;
			else	//递减
				l = mid;
		}
		printf("%.4lf\n", js(l));
	}
	
	return 0;
}

取巧法

观察题目及备注我们可以发现，x 的变化范围 (0, 100] 精度在 1e-4 上，100 * 10⁴ = 10⁶。若只有一组数据的话，完全是可以通过枚举 x 来找到最小值，但题目并没有说明组数的多少，所以这样的方法是有风险的。

尽量减少 pow 函数的使用！
尽量减少 pow 函数的使用！
尽量减少 pow 函数的使用！
为了使程序的效率更高，我们应当避免使用 pow 函数，直接用多个连乘来替代 pow 函数，否则也是不能通过全部测试样例。

实现代码

#include<bits/stdc++.h>
using namespace std;
double y;
double f(double x){
    return 7*x*x*x*x*x*x*x+6*x*x*x*x*x*x+2*x*x*x+8*x*x-y*x;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
      scanf("%lf",&y);
      double ans=f(0.0001);
      for(double i=0.0001; i<=100; i+=0.0001)
          ans=min(ans,f(i));
      printf("%.4lf\n",ans);
    }
    return 0;
}

总结

三分法编写代码比较麻烦，通过测试样例，需要 3 ms。
取巧法编写代码简单，通过测试样例，需要 237 ms。
两种方法，各有所长…