修理牛棚_(贪心，逆转)

原题链接：1349. 修理牛棚 - AcWing题库

题意：给定有牛的牛棚，要把所有这些牛棚用数量有限的木板挡住，要怎么挡所用的木板的长度最小

思路

发现： 首先有牛的牛棚一定要挡

挡了之后要长度最小，那就把木板数量用到极致，用得越多，链接的越少，长度就越短，但是注意满足所有牛都挡住之后不应该再有更多木板，即木板最多用给的那个的牛的数量

怎么用木板？ 发现既然有牛的棚都必须要有木板，那么要长度最小，就从相邻的牛棚里找最近的，连接起来省掉一块木板，这样增加的长度最小——属于贪心，每次找最近

即思路为：先把牛都分别用上木板，找最近的合并，省去木板，一直到木板满足约束

正着找很难，不如逆转一下，先盖住牛，再减木板

实现

用小根堆做

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
 
using namespace std;
 
const int N = 210;
int c[N];
int n, s, C;
priority_queue<int, vector<int>, greater<int>> q;
 
int main()
{
    cin >> n >> s >> C;
    
    for(int i = 1; i <= C; i ++)
    {
        cin >> c[i];
    }
    sort(c + 1, c + C + 1);
    //int cnt = 0;
    for(int i = 2; i <= C; i ++)
    {
        //cnt ++;
        if(c[i] - c[i-1] > 1)
            q.push(c[i] - c[i-1] - 1);
        
    }
    
    int ans = C;
    // cout << q.size();
    // cout << n;
    while((int)q.size() - n + 1 > 0)
    {
        ans += q.top();
        q.pop();
    }
    
    cout << ans << endl;
    
    return 0;
}