題目鏈接: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;
}