題目鏈接:http://ace.delos.com/usacoprob2?a=h9vkjno3LrX&S=barn1如果只能使用一塊木板，那就要從第一個(gè)有奶牛的stall到最后一個(gè)有奶牛的stall.
因?yàn)檫@一塊長(zhǎng)木板中間,可能會(huì)有空的stall,所以會(huì)浪費(fèi)了木板.
如果可以使用兩塊木板,我們就可以在這塊長(zhǎng)木板中間挖一個(gè)洞,這樣木板總長(zhǎng)度就減小了這個(gè)洞的長(zhǎng)度.
很明顯,要木板總長(zhǎng)度最小,就挖掉最大的那個(gè)洞.
能購(gòu)買(mǎi)m塊木板,也就是說(shuō)可以挖m-1個(gè)洞.將洞的長(zhǎng)度從大到小排序,挖掉最大的m-1個(gè)洞即可.
#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的時(shí)候仍然成立
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;
}