【二分搜索】HDU-2899 Strange fuction
代码
#include <iostream>
#include <math.h>
using namespace std;
const double L = 1e-8;
double binarySearch(double Y) {
double left = 0;
double right = 100;
while(right-left>L) {
double mid = (left+right)/2.0;
double tmp = 42*pow(mid, 6) + 48*pow(mid, 5) + 21*pow(mid, 2) + 10*mid - Y;
if(tmp>L) {
right = mid;
} else if(tmp<-1*L) {
left = mid;
} else {
return mid;
}
}
return left;
}
int main() {
int T;
scanf("%d", &T);
for(int i=0; i<T; i++) {
double Y;
scanf("%lf", &Y);
double x = binarySearch(Y);
double ans = 6*pow(x, 7) + 8*pow(x, 6) + 7*pow(x, 3) + 5*pow(x, 2) - Y*x;
printf("%.4lf\n", ans);
}
return 0;
}
注解
1、先求导,易知在[0,100]先减后增,有唯一一个导数为零的点。因此在[0,100]的最小值点,就是导数为零的点。
2、找原函数最小值,对此题来说也就是找导数为零的点。用二分法求。
3、求出最小值点后,再代入原函数,即可求出函数的最小值。