【二分搜索】HDU-2899 Strange fuction

【二分搜索】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、求出最小值点后,再代入原函数,即可求出函数的最小值。

结果

【二分搜索】HDU-2899 Strange fuction