38 修理牛棚

问题描述 :

在一个暴风雨的夜晚，农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚（牛棚的总数S:1<= S<=200）没有住满。 剩下的牛一个紧挨着另一个被排成一行安置在有屋顶的牛棚来过夜。 所以有些牛棚里有牛，有些没有。

所有的牛棚有相同的宽度，且宽度设为1。 因为有些门遗失，农民约翰需要架起新的木板作为门。 他的新木材供应者将会供应他任何他想要的长度,但是供应者只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。

计算拦住所有有牛的牛棚所需木板的最小总长度。

输出所需木板的最小总长度作为的答案。

说明：拦住一个牛棚需要的木板长度为1，拦住相邻的三个牛棚则需要木板长度为3。

比如有牛的牛棚编号为：

3 5 8 10 11

并且只能使用两块木板，

则第一块木板从3到5，长度为3，

第二块木板从8到11，长度为4，

因此，需要木板的总长度为7。

输入说明 :

第 1 行: M 和 C(用空格分开)

第 2 到 C+1行: 每行包含一个整数，表示牛所占的牛棚的编号。

其中：

可能买到的木板最大的数目：M(1<= M<=50);

需要安置的牛的数目C(1<= C <=S)

安置后牛所在的牛棚的编号stall_number(1<= stall_number <= S)。

输出说明 :

单独的一行包含一个整数表示所需木板的最小总长度

输入范例 :

3 5
2
4
6
8
7

输出范例 :

5

c源码：

#include
int main()
{int i,j,n,m,a[220],t,s,b[220],max;while(scanf("%d%d",&m,&n)!=EOF){  memset(a,0,220);memset(b,0,220);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)for(j=0;j<n-i-1;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}for(i=0;i<n-1;i++){ b[i]=a[i+1]-a[i];}//间距for(i=0;i<n-1;i++)for(j=0;j<n-i-2;j++)if(b[j]<b[j+1]){t=b[j];b[j]=b[j+1];b[j+1]=t;}t=1;//一块木板s=a[n-1]-a[0]+1;//最大长度i=0;while(t<m&&i<n-1){ if(b[i]>1){s=s-b[i]+1;t++;}i++;}printf("%d\n",s);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！