分治

分解為小問題 合併結果

分治

/*
 * AP325
 * P-1-3. 棍子中點切割
*/
#include <bits/stdc++.h>
using namespace std;

int cut(vector<long long int>& a, int l, int r) {
	if (r - l <= 1) return 0;
	int len = a[r]-a[l] , k = (a[l]+a[r])/2;
	int m = (l + r)/2;
	while (a[m]<k){
		m++;
	}
    if (a[m-1]-a[l] >= a[r]-a[m]){
        m--; 
    }
    return (len) + cut(a, l, m) + cut(a, m, r);
}

int main() {
    int N, L;
    cin >> N >> L;
    vector<long long int> a(N + 2);
    a[0] = 0;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }
    a[N + 1] = L;
    cout << cut(a, 0, N + 1) << endl;
    return 0;
}