USACO training 1.4 修理牛棚
补集思想的应用：求最短的板子长度只要依次减去最长的空隙长度（贪心）

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long  LL;
const int N = 210;
int a[N], b[N]; // b存储空隙
int m,s,c;
int main( ) {
    scanf("%d %d %d", &m, &s, &c);
    for ( int i = 0; i < c; i++ ){
        scanf("%d", &a[i]);
    }
    sort(a, a + c);
    int res =  a[c-1] - a[0] + 1; // 先求覆盖所有牛的板子再减去空隙断开
    for ( int i = 1; i < c; i++ ) b[i] = a[i] - a[i-1] - 1; // 求空隙数多减1
    sort(b + 1, b + c, greater<int>()); // 排序空隙，大的空隙在前
    // 补集思想，先求空隙，依次减去最大的空隙
    for ( int i = 1; i <= m -1 && i < c; i ++ ) {
        res -= b[i];
    }
    cout << res;
    return 0;


}