D_2_Chopping_Carrots_Hard_Version.cpp

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;

const int N = 1e5 + 5;
int m[N];

/*

iterating over v -> minimum value of ai/pi
for each v -> need minimum possible maximum value of ai/pi >= v 
this equal (prefix max of m[v] ) = M[v]


*/

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for(int i=0;i<n;i++) {
        cin >> v[i];
    }
    int A = v[0];
    for(int i=0;i<=A;i++) m[i] = 0;

    for(int i=0;i<n;i++) {
        int prev = inf;
        for(int l=1, r;l <= min(k, v[i]); l =  r + 1) {
            int q = v[i] / l;
            r = v[i] / q;
            // For all v ≥ (q+1), this element enforces M(v) ≥ prev
            m[q + 1] = max(m[q + 1], prev);
            prev = q;
        }
        m[0] = max(m[0], prev);
    }

    vector<int> M(A + 1);
    int mx = 0;
    for(int i=0;i<=A;i++) {
        mx = max(mx, m[i]);
        M[i] = mx;
    }

    int ans = inf;
    for(int v=0;v<=A;v++) {
        ans = min(ans, M[v] - v);
    }

    cout << ans << "\n";

}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int _;
    cin >> _;
    while (_-->0) {
        solve();
    }

    return 0;
}