LHPC 2016 pB. 剪紙 ( Binary Search )

最大最小值問題十之八九是二分搜。能剪的次數和最短紙的最長長度，顯然成單調關係，因此可以用二分搜處理。注意最短長度的上界是原先的最短長度，還有要開 long long。

bool ok( const vi &L, const int K, int x ){
    ll cnt = 0;
    for( int i = 0; i < L.size(); ++i ){
        if( L[ i ] < x ) return false;
        cnt += L[ i ] / x - 1;
    }
    return cnt >= K;
}

void solve(){
    int N, K; cin >> N >> K;
    vi L( N );
    for( int i = 0; i < N; ++i )
        cin >> L[ i ];
    sort( L.begin(), L.end(), greater< int >() );
    int lb = 1, rb = *min_element( L.begin(), L.end() );
    int ans = -1;
    while( lb <= rb ){
        int mid = ( lb + rb ) / 2;
        if( ok( L, K, mid ) ) ans = mid, lb = mid + 1;
        else rb = mid - 1;
    }
    cout << ans << "\n";
}