首页 > 代码库 > 【USACO 1.3】Barn Repair

【USACO 1.3】Barn Repair

贪心,去掉最大的min(m,c)-1个间隔

/*******************************************  TASK: barn1  LANG: C++   Created Time: 2016/9/9 14:36:17 *********************************/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int a[201],d[201];int main(){	freopen("barn1.in","r",stdin);	freopen("barn1.out","w",stdout);	int m,s,c;	cin>>m>>s>>c;	for(int i=0;i<c;i++)cin>>a[i];	sort(a,a+c);	int ans=a[c-1]-a[0]+1;	for(int i=1;i<c;i++)		d[i]=a[i]-a[i-1]-1;			sort(d+1,d+c);	for(int i=1;i<min(m,c);i++)		ans-=d[c-i];	cout<<ans<<endl;	}

  

【USACO 1.3】Barn Repair