【正经题解】修理牛棚

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_BARNS = 205;

int barns[MAX_BARNS];
int gaps[MAX_BARNS];

// 降序排序的比较函数
bool compare(int p, int q) {
    return p > q;
}

int main() {
    int maxWood, totalBarns, occupiedBarns;
    cin >> maxWood >> totalBarns >> occupiedBarns;

    if (maxWood >= occupiedBarns) {
        cout << occupiedBarns;
        return 0;
    }

    // 牛占用的牛棚编号
    for (int i = 1; i <= occupiedBarns; i++) {
        cin >> barns[i];
    }

    // 对牛占用的牛棚编号进行排序
    sort(barns + 1, barns + occupiedBarns + 1);

    // 计算相邻牛棚之间的间隔
    for (int i = 1; i < occupiedBarns; i++) {
        gaps[i] = barns[i + 1] - barns[i];
    }

    // 对间隔进行排序，以便使用最大的间隔
    sort(gaps + 1, gaps + occupiedBarns, compare);

    int minWood = barns[occupiedBarns] - barns[1] + maxWood;

    // 使用最大的间隔填充，直到使用完指定数量的木板
    for (int i = 1; i < maxWood; i++) {
        minWood -= gaps[i];
    }

    cout << minWood;

    return 0;
}