文字教学

这道题用贪心算法解决，核心思路是“先盖所有连续区间，再在最大的空隙处断开以节省木板长度”：

1. 先将有牛的牛棚编号排序，方便计算连续区间和空隙。
2. 初始用1块木板盖住从第一个到最后一个有牛的牛棚，计算初始总长度。
3. 计算每两个相邻有牛的牛棚之间的空隙（空牛棚数量），将空隙从大到小排序。
4. 每多1块木板，就可以在1个最大的空隙处断开（不盖这个空隙），从而减少总长度。最多用m块木板，就减去前(m-1)个最大的空隙。

代码

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

int a[205], b[205];

int main() {
    int m, s, c, ans, cnt = 0;
    cin >> m >> s >> c;
    for (int i = 0; i < c; ++i) cin >> a[i];
    
    // 排序牛棚编号
    for (int i = 0; i < c - 1; ++i)
        for (int j = 0; j < c - 1 - i; ++j)
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
    
    ans = a[c - 1] - a[0] + 1;
    
    // 计算相邻空隙
    for (int i = 1; i < c; ++i)
        b[cnt++] = a[i] - a[i - 1] - 1;
    
    // 空隙从大到小排序
    for (int i = 0; i < cnt - 1; ++i)
        for (int j = 0; j < cnt - 1 - i; ++j)
            if (b[j] < b[j + 1]) swap(b[j], b[j + 1]);
    
    // 减去前m-1个最大空隙
    for (int i = 0; i < m - 1 && i < cnt; ++i)
        ans -= b[i];
    
    cout << ans << endl;
    return 0;
}