HDU 2899 Strange Function：求導 + 二分查找最小值

題目

函數 F(x) = 6x⁷ + 8x⁶ + 7x³ + 5x² - y·x，x∈[0,100]。給定 y，求最小值。

數學解法

求導：F'(x) = 42x⁶ + 48x⁵ + 21x² + 10x - y。
導函數 g(x)=42x⁶+48x⁵+21x²+10x 在 [0,100] 嚴格遞增，範圍 [0, 10¹³]。對任意 y，方程 g(x)=y 有唯一解 x₀。
x < x₀ 時 F' < 0（遞減），x > x₀ 時 F' > 0（遞增）。故 F(x₀) 為全局最小值。
二分查找 x₀ 於 [0,100]，精度 1e-6，代入 F(x) 輸出。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
double F(double x, double y) {
    return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;
}
double Fprime(double x, double y) {
    return 42*pow(x,6)+48*pow(x,5)+21*pow(x,2)+10*x-y;
}
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        double y; scanf("%lf", &y);
        double l = 0, r = 100;
        for (int iter = 0; iter < 100; iter++) { // 固定次數二分
            double mid = (l+r)/2;
            if (Fprime(mid, y) > 0) r = mid;
            else l = mid;
        }
        printf("%.4f\n", F((l+r)/2, y));
    }
    return 0;
}