题目链接:http://ace.delos.com/usacoprob2?a=h9vkjno3LrX&S=barn1如果只能使用一块木板，那就要从第一个有奶牛的stall到最后一个有奶牛的stall.
因为这一块长木板中间,可能会有空的stall,所以会浪费了木板.
如果可以使用两块木板,我们就可以在这块长木板中间挖一个洞,这样木板总长度就减小了这个洞的长度.
很明显,要木板总长度最小,就挖掉最大的那个洞.
能购买m块木板,也就是说可以挖m-1个洞.将洞的长度从大到小排序,挖掉最大的m-1个洞即可.
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("barn1.in");
ofstream fout("barn1.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
void solve()
{
int m,s,c;
in>>m>>s>>c;
//v保存有牛的stall
vector<int> v(c);
for(int i=0;i<c;++i)
in>>v[i];
sort(v.begin(),v.end());
// space保存所有的洞
vector<int> space;
for(int i=1;i<c;++i){
if(v[i]-v[i-1]-1!=0){
space.push_back(v[i]-v[i-1]-1);
}
}
sort(space.begin(),space.end(),greater<int>());
//由于v的大小>=1。v==1的时候仍然成立
int total_len = v[v.size()-1]-v[0]+1;
m-=1;
for(int i=0;i<space.size();++i){
if(m>0){
total_len -=space[i];
m--;
}
}
out<<total_len<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}