P1209 [USACO1.3]修理牛棚 Barn Repair(贪心+逆向思维)

我们可以先假设只有一块木板从编号最小的牛棚一直铺到编号最大的牛棚，然后断开m-1处。自然要按相邻牛棚的编号差从大到小断开才能使我们断开的地方可以有效节省木板长度（因为中间省去的要更多）
另外，要将输入的数据排序，数据可能不是按编号从小到大给的

#include<algorithm>
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define debugs(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl
const ll N=5e5+7;
const ll base=137;
const ll mod=2147483647;
template<typename T>inline T read(T &x)
{
    x=0;ll f=1;char c;
    while(!isdigit(c=getchar()))if(c=='-')f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
bool cmp(ll a,ll b)
{
    return a>b;
}
ll n,m,s,c,a[N],b[N],ans;
int main()
{
    read(m),read(s),read(c);
    for(int i=1;i<=c;++i)
        read(a[i]);
    if(m>c){cout<<c<<endl;return 0;}
    sort(a+1,a+1+c);
    ans=a[c]-a[1]+1;
    for(int i=2;i<=c;++i)
        b[i]=a[i]-a[i-1]-1;
    sort(b+1,b+1+c,cmp);
    for(int i=1;i<m;++i)
        ans-=b[i];
    cout<<ans<<endl;
    return 0;
}