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

た入场券 2022-12-19 08:52 105阅读 0赞

### [炎炎夏日][Link 1] ###

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

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

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

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

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

--------------------

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

#### 三分法 ####

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

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

大概模拟图  
![模拟图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
实现代码

#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 \* 104 = 106。若只有一组数据的话，完全是可以通过枚举 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。  
两种方法，各有所长…

[Link 1]: https://ac.nowcoder.com/acm/contest/8889/I
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/752c33f545ca40f6ac8f6e7f209fe308.png