问题描述 :
在一个暴风雨的夜晚，农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚（牛棚的总数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 524687
输出范例：
5解题思路：
此题意思为：给定木板的数量和牛棚的序号，将牛棚用木板连接起来，求出木板的总长度的最小值。
比如：
1个木板，5个牛棚分别为3、5、8、10、11
则用两个木板连接5个牛棚，最短解法是 3、4 、8、10、11 ，总长度为 9，即 11 - 3 + 1；
再比如：
2个木板，5个牛棚分别为3、5、8、10、11
多出来一条木板，我们肯定想把间距最小的几个连在一起，我们先求出每个木板之间的间隔为2、3、2、1；
显然编号5和8之间间隔3，间隔最大，故将3去除，即 9 - 3 + 1 = 7；
故最短解法是 3、5 、8、10、11 ，总长度为 7 ，第一块木板（4-3+1）= 3，第二块木板长 （11-8+1）= 4；
解题步骤：
所以本题首先要将木板按编号排序，再求出所有的木板之间的间距，将间距也排序，
先假设有一块木板，再减去最大的间距，减去次大的间距，……，直到达到最大木板数。
最后比如：
3个木板，5个牛棚分别为2、4、6、8、7
- 木板排序：[2,4,6,7,8]
- 求间距：[2,2,1,1]
- 间距排序：[2,2,1,1]
- 假设只有一块木板，总长 8-2+1=7；
- 有两块木板，减去最大间隔，总长 7-2+1=6；
- 有三块木板，减去次大间隔，总长 6-2+1=5；
代码参考：
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>#define MAX_SIZE 200/* 升序 */
int compAsc(const void *a, const void *b)
{return *(int *)a - *(int *)b;
}/* 降序 */
int compDes(const void *a, const void *b)
{return *(int *)b - *(int *)a;
}int main()
{// m = 木板最大数量，c = 牛/牛棚的数量int m, c, woodNum[MAX_SIZE], distance[MAX_SIZE], i, total;scanf("%d %d", &m, &c);for (i = 0; i < c; i++){scanf("%d", &woodNum[i]);}if (m > c) //木板数大于牛棚数，不用分，每个牛棚一个木板{printf("%d\n", c);return 0;}qsort(woodNum, c, sizeof(int), compAsc);for (i = 0; i < c - 1; i++){distance[i] = woodNum[i + 1] - woodNum[i];}qsort(distance, c - 1, sizeof(int), compDes);//假设只有一个木板total = woodNum[c - 1] - woodNum[0] + 1;// 逐个减去最大间隔for (i = 0; i < m - 1; i++){total = total - distance[i] + 1;}printf("%d\n", total);return 0;
}