class Solution {
    int [][] memo = new int [101][10001];
    
    public int superEggDrop(int k, int n) {
        if (k == 1) return n;
    
        if(memo[k][n] != 0){
            return memo[k][n];
        }
        
        int ans = n;
        int l = 1;
        int r = n;
        while (l < r) {
            int h = (l + r) >> 1;
            
            int lower = superEggDrop(k - 1, h - 1); // 往下需要的次數
            int higher = superEggDrop(k, n - h); // 往上需要的次數
            
            int v = Math.max(lower, higher); // 考慮 worst case
            ans = Math.min(ans, v + 1);
            
            if(lower == higher){
                break;
            }else if(lower > higher){
                r = h;
            }else{
                l = h + 1;
            }
            
        }
        memo[k][n] = ans;
        
        return ans;
    }
}

最大值最小化問題

數線上 n 個點, 用 K 個線段覆蓋，最長的線段長度要愈小愈好
x = [1 3 4 | 7 8 9 13]
K = 2

#include <iomanip>
#include <iostream>

using namespace std;

long double f(long double x) {
    return 3 * x * x + 5 * x + 1;
}

long double fp(long double x) {
    return 6 * x + 5;
}

int main() {
    long double l = -1e9, r = 1e9;
    long double x = r;

    for (int i = 0; i < 60; i++) {
        long double mid = (l + r) / 2;

        x -= f(x) / fp(x);

        long double delta = 1e-9;
        if (f(mid + delta) - f(mid) > 0) {
            r = mid;
        } else {
            l = mid;
        }
        cout << fixed << setprecision(20);
        cout << i << ' ' << x << ' ' << f(x) << '\n';
        cout << i << ' ' << l << ' ' << r << ' ' << f(r) << '\n';
    }

    return 0;
}