P1209 [USACO1.3]修理牛棚 Barn Repair
分析:贪心,取对间隔进行排序,按照贪心思想取间隔最大着为空隙,当前所需木板数+1,要注意的是一旦选出空隙总长要加一,因为你分裂了线段少算了末端,木板数用完了就得到答案了..上一个 个人认为很短的代码,看的很容易理解的.
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d[201],e[201],ans;
bool cmp(int j,int k){return j>k;}
int main()
{
cin>>a>>b>>c;
for(int i=1;i<=c;i++)
{
cin>>d[i];
}
if(a>c){cout<<c;return 0;}
sort(d+1,d+1+c);
for(int i=2;i<=c;i++)
{
e[i]=d[i]-d[i-1];
}
sort(e+2,e+1+c,cmp);
ans+=a;
for(int i=2+a-1;i<=c;i++)ans+=e[i];
cout<<ans;
return 0;
}