Rday2

Rday2

二分

Strange fuction

Now, here is a fuction:
F(x) = 6 x^7+8x^6+7x^3+5x^2-y*x (0 <= x <=100)
Can you find the minimum value when x is between 0 and 100.
Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line has only one real numbers Y.(0 < Y <1e10)
Output
Just the minimum value (accurate up to 4 decimal places),when x is between 0 and 100.

1
2
3
4
5
6
7
Sample Input
2
100
200
Sample Output
-74.4291
-178.8534

题解

1
2
3
4
这道题就是一个数学思维题
相当于y是个常数求 F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100)这个函数的最小值,令F' = 0,得出x,y的方程,
用二分法解方程得x0(易证得x0>=0 && x0<=100),则F'(x0) = 0,由F'' 在[0-100]上恒大于0
所以F'在[0-100]上单增,所以F'(x)<0(x<x0),F'(x)>0(x>x0),所以F(x)在x=x0处取得最小值,所以本题主要就是二分求解方程的x0,然后直接带入x0,y计算即可。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
const double mod = 1e-6;

double qiu_y(double x)
{
return 42 * pow(x, 6.0) + 48 * pow(x, 5.0) + 21 * pow(x, 2.0) + 10 * x;
}
double f(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;
double l, r, mid, y, res;
cin >> t;
while(t --)
{
cin >> y;
l = 0.0, r = 100.0;
while(r - l > mod)
{
mid = (r + l) / 2;
res = qiu_y(mid);
if(res < y)
{
l = mid + 1e-8;
}
else
{
r = mid - 1e-8;
}
}
printf("%0.4lf\n",f(mid, y));
}
return 0;
}

---------------- The End ----------------
0%