Freight Train

#include<bits/stdc++.h>
using namespace std;

int T, n, w, l;
int d[10010];

bool ok(int x) {
    int start = 1;
    int idx = 0;
    int s = 0;
    while (start <= n) {
        if (idx >= w || d[idx] - start > x){
            s ++;
            if (idx < w) 
                start = d[idx];
            else start = n+1;
        } else {
            start += x;
            s ++;
            while (idx < w && d[idx] < start)
                idx ++;
        }
    }
    return s <= l;
}

int main() {
    cin >> T;
    while (T--) {
        cin >> n >> w >> l;
        for (int i = 0; i < w; i++)
            cin >> d[i];
        int l = 1; 
        int r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (ok(mid))
                r = mid;
            else l = mid+1;
        }
        cout << l << endl;
    }
    
    
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED