卢俊达

题目大意：

有s个牛棚，其中c个有牛，共有m个任意长度的木板用来封住所有有牛的牛棚。要求编程求出至少需要多长的木板。

思路：

尽量增加木板数量以节约木板长度，最佳情况是一个木板封住一个有牛的牛棚，即用c个木板。总长度为c个单位长度。

若木板数量小于c，那么最多可以用m个木板。可以想象为将一个“从序号最小的牛棚一直到序号最大的牛棚的全部封住的木板”分成m份，也就是去掉其中m-1段。

按照贪心思想，应该按由大到小顺序去掉前m-1个“两个相邻有牛的牛棚之间的间隔”。

代码：

/*
ID: lujunda1
LANG: C++
PROG: barn1
*/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
using namespace std;
int stalls[200],dis[200];
//自定义cmp比较函数，从大到小排序。 
int cmp(const void* m,const void* n)
{
	return *(int*)n-*(int*)m;
}
int main()
{
	freopen("barn1.in","r",stdin);
	freopen("barn1.out","w",stdout);
	//分别用min和max记录序号最小和最大的牛棚。 
	int m,s,c,min=200,max=0;
	scanf("%d%d%d",&m,&s,&c);
	for(int i=0;i<c;i++)
	{
		scanf("%d",&stalls[i]);
		min=min<stalls[i]?min:stalls[i];
		max=max>stalls[i]?max:stalls[i];
	}
	//当最大木板数量大于等于有牛的牛棚的数量时，可以用一个木板补一个牛棚。 
	if(m>=c)
	{
		printf("%d\n",c);
		return 0;
	}
	//有牛的牛棚的序号可能不是按照顺序给出的，因此需要排序。 
	qsort(stalls,c,sizeof(stalls[0]),cmp);
	//将两个牛棚之间的间隔存储起来并按由大到小顺序排序。 
	for(int i=0;i<c-1;i++)
		dis[i-1]=stalls[i-1]-stalls[i]-1;
	qsort(dis,c-1,sizeof(dis[0]),cmp);
	//sum表示从最小序号的牛棚到最大序号的牛棚所需最长的木板。 
	int sum=max-min+1;
	//把一个最长的连续木板分成m份需要去掉中间m-1个部分。
	//贪心思想是按照由大到小顺序去掉其中前m-1个间隔。 
	for(int i=0;i<m-1;i++)
		sum-=dis[i];
	printf("%d\n",sum);
}