Barn Repair（贪心）

Barn Repair

It was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer John's cows. Happily, many of the cows were on vacation, so the barn was not completely full.

The cows spend the night in stalls that are arranged adjacent to each other in a long line. Some stalls have cows in them; some do not. All stalls are the same width.

Farmer John must quickly erect new boards in front of the stalls, since the doors were lost. His new lumber supplier will supply him boards of any length he wishes, but the supplier can only deliver a small number of total boards. Farmer John wishes to minimize the total length of the boards he must purchase.

Given M (1 <= M <= 50), the maximum number of boards that can be purchased; S (1 <= S <= 200), the total number of stalls; C (1 <= C <= S) the number of cows in the stalls, and the C occupied stall numbers (1 <= stall_number <= S), calculate the minimum number of stalls that must be blocked in order to block all the stalls that have cows in them.

Print your answer as the total number of stalls blocked.

PROGRAM NAME: barn1

INPUT FORMAT

Line 1:	M, S, and C (space separated)
Lines 2-C+1:	Each line contains one integer, the number of an occupied stall.

SAMPLE INPUT (file barn1.in)

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

OUTPUT FORMAT

A single line with one integer that represents the total number of stalls blocked.

SAMPLE OUTPUT (file barn1.out)

25

[One minimum arrangement is one board covering stalls 3-8, one covering 14-21, one covering 25-31, and one covering 40-43.]

   题意：

   最大供应木块数为M（1到50）（每块木头的提供的长度无限长），牛棚数一共有S（1到200）个，总共有C头牛（大于1小于S），给出没头牛所以在牛棚编号，求在不超过最大供应木块数的情况下，木块能把全部牛都封住的最小长度。

 

   思路：

   将木头数与牛的数量进行对比，分成三种情况：

   1.当木头数M>牛的数量C（木头数不等于1），则最小长度就是每头牛都有自己的一扇门，故最小长度就是牛的数量；

   2.当木头数M=1的时候，故只能把门从头修到尾，故最小长度就是编号最大的牛-编号最小的牛+1；

   3.当木头数M<牛的数量C（木头数不等于1），则最小长度应该是全部木板都能用到的时候，则求法为：在C-1个空隙中，取最大空隙长度的前M-1个间隔，然后分别算每段木头的长度加和起来就可以了。

 

 First and test：

/*
TASK:barn1
LANG:C++
ID:sum-g1
*/
#include<cstdio>
#include<map>
#include<algorithm>

using namespace std;

int main()
{
freopen("barn1.in","r",stdin);
freopen("barn1.out","w",stdout);	
int M,S,C,i,sum;
	int number[205];
	int cut[55];
	multimap<int,int> m;
	scanf("%d%d%d",&M,&S,&C);
	for(i=1;i<=C;i++)
	 scanf("%d",&number[i]);
	 
	sort(number+1,number+C+1); 
	
	if(M==1) printf("%d\n",number[C]-number[1]+1);
	else
	{
	for(i=2;i<=C;i++)
	  	m.insert(pair<int,int>(number[i]-number[i-1],i-1));
	  
	multimap<int,int>::iterator it;
    it=m.end();	
	
	for(i=0,it--;i<M-1;i++,it--)
	   cut[i]=it->second;
    
    sort(cut,cut+M-1);
	
	sum=number[cut[0]]-number[1]+1;
  
    for(i=1;i<M-1;i++)
      sum+=(number[cut[i]]-number[cut[i-1]+1]+1);
	
	sum+=(number[C]-number[cut[M-2]+1]+1);
	
    printf("%d\n",sum);
       }
	exit(0);
}
//忽略了两个情况
//提供的木板不一定要全部用完
//当只有一块木板提供的时候

  AC： 

/*
TASK:barn1
LANG:C++
ID:sum-g1
*/
#include<cstdio>
#include<map>
#include<algorithm>

using namespace std;

int main()
{
freopen("barn1.in","r",stdin);
freopen("barn1.out","w",stdout);	
int M,S,C,i,sum;
	int number[205];
	int cut[55];
	multimap<int,int> m;
//用multimap的对应关系来存储每个棚间的间隙和间隙左侧的棚序号
//不用map是因为map会去重
	scanf("%d%d%d",&M,&S,&C);
	for(i=1;i<=C;i++)
	 scanf("%d",&number[i]);
	sort(number+1,number+C+1); 
//对棚的序号进行由小到大的排序	
	if(M==1) printf("%d\n",number[C]-number[1]+1);
//下面的条件要加上M!=1
	if(M!=1&&M>=C) printf("%d\n",C);
	if(M!=1&&M<C)
	{
	for(i=2;i<=C;i++)
	  	m.insert(pair<int,int>(number[i]-number[i-1],i-1));
//multimap的赋值处理要注意
	multimap<int,int>::iterator it;
       it=m.end();	
	for(i=0,it--;i<M-1;i++,it--)
	   cut[i]=it->second;
//因为切点间隙已经由小到大排好序了，所以从最后一项开始向前取M-1个空隙的左序号放在cut数组中
    sort(cut,cut+M-1);
//对cut进行由小到大排序
	sum=number[cut[0]]-number[1]+1;
    for(i=1;i<M-1;i++)
      sum+=(number[cut[i]]-number[cut[i-1]+1]+1);	
	sum+=(number[C]-number[cut[M-2]+1]+1);	
//总加和操作即可求出得数
//注意边界问题，哪里该+1还是不该+1
    printf("%d\n",sum);
       }
	exit(0);
}

   总结：

   题目不难，但是却也是过了一天才回过头再去看这个题。一开始是因为读不懂题意，没有耐心看下去，所以才一直被搁置在一旁。静下来很重要，慢慢的发现在实验室和在宿舍真的会有差别，平静很重要，专心更加重要。