USACO-section1.3 Barn Repair

题意： John 需要为牛棚安装木板来看住牛，木板长度不限但是数量有限。 给出可能买到的木板最大的数目M(1<= M<=50); 牛棚的总数S(1<= S<=200); 牛棚里牛的总数C(1 <= C <=S); 和牛所在的牛棚的编号stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度 输出所需木板的最小总长度作为答案

题解： 1前提：要使总长度小，就要使用尽量多的木板。

2所有牛按编号排序（虽然样例中是排好序的）； 假设从第一头牛到最后一头牛用一块木板； 相邻两头牛之间间距排序，找出前M-1大的间距和去除，就能得到最小总长度；

3注意：如果M大于C，一头牛一块木板，直接输出C，

/*
ID:jsntrdy1
PROG: barn1
LANG: C++
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<fstream>
#include<algorithm>
const int N=210;
using namespace std;
ifstream fin("barn1.in");
ofstream fout("barn1.out");
int main()
{
    int m,s,c,res;
    int a[N];//c头牛所在牛棚号 
    int b[N];//记录相邻两头牛的距离 
    fin>>m>>s>>c;
    if(m>c)
    {
      fout<<c<<endl;
      return 0;
    }
    for(int i=0;i<c;i++)
    {
        fin>>a[i];
    }
    sort(a,a+c);//***************

    for(int i=0;i<c-1;i++)
    {
        b[i]=a[i+1]-a[i];
    } 
    sort(b,b+c-1);
    res=a[c-1]-a[0]+m;
    for(int i=c-2;i>=c-m;i--)
    {
        res-=b[i];
    }
    fout<<res<<endl;
    return 0;
}