寒假专题一(二分、三分)

题解

题目链接：https://vjudge.net/contest/147539

A - Strange fuction

题目大意

F(x) = 6 * x^7 + 8 * x^6 + 7 * x^3 + 5 * x^2 - y * x (0 <= x <= 100)，求出最小值

Input

第一行包含测试用例组数 T (0<=T<=100)，后面的 T 行都只包含一个实数 Y

Output

求出最小值，精确到小数点后四位

Sample Input

2
100
200

Sample Output

-74.4291
-178.8534

解题思路

**二分查找**
导函数在 [0,100] 之间显然大于0，因此原函数递增，只需要利用二分查找求出当 F'(x)=0 时的 x 值，再求出 F(x) 即可

代码

#include <stdio.h>
#include <math.h>
int main()
{
    int i, T;
    double Y, ans, l, r, mid;
    scanf("%d", &T);
    for(i=0;i<T;i++)
    {
        scanf("%lf", &Y);
        l = 0;
        r = 100;
        mid = (l+r)/2;
        while(fabs(42*pow(mid,6)+48*pow(mid,5)+21*pow(mid,2)+10*mid-Y)>1e-6)
        {
            if(42*pow(mid,6)+48*pow(mid,5)+21*pow(mid,2)+10*mid-Y<-1e-6)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
            mid = (l+r)/2;
        }
        ans = 6*pow(mid,7)+8*pow(mid,6)+7*pow(mid,3)+5*pow(mid,2)-Y*mid;
        printf("%.4lf\n", ans);
    }
    return 0;
}

该题收获

1. 熟悉了二分查找
2. pow()的返回值和传入值的数据类型都为double，因而 long double 的值传不进去