1.4.2 USACO Barn Repair（贪心）

Bertha 。 2023-07-17 06:22 43阅读 0赞

# 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 ###

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

### 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) ###

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

翻译：[修理牛棚][Link 1]

## 题目描述 ##

在一个月黑风高的暴风雨夜，Farmer John 的牛棚的屋顶、门被吹飞了 好在许多牛正在度假，所以牛棚没有住满。

牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。

自门遗失以后，Farmer John 必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度，但是吝啬的供应商只能提供有限数目的木板。 Farmer John 想将他购买的木板总长度减到最少。

给出 m,s,cm,s,c，表示木板最大的数目、牛棚的总数、牛的总数；以及每头牛所在牛棚的编号，请算出拦住所有有牛的牛棚所需木板的最小总长度。

## 输入格式 ##

一行三个整数 m,s,cm,s,c，意义如题目描述。  
接下来 cc 行，每行包含一个整数，表示牛所占的牛棚的编号。

## 输出格式 ##

输出一行一个整数，表示所需木板的最小总长度。

## 输入输出样例 ##

**输入 \#1**复制

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

**输出 \#1**复制

## 说明/提示 ##

【数据范围】  
对于 100\\%100% 的数据，1\\le m \\le 501≤m≤50，1\\le c \\le s \\le 2001≤c≤s≤200。

USACO Training Section 1.3

> 解析：
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]
> 
> （一）木板数多于所占牛棚数
> 
> <table style="width:85pt;"> 
>  <tbody> 
>   <tr> 
>    <td style="vertical-align:middle;width:17pt;"><span style="color:#000000;">1</span></td> 
>    <td style="vertical-align:middle;width:17pt;"><span style="color:#000000;">2</span></td> 
>    <td style="vertical-align:middle;width:17pt;"><span style="color:#000000;">3</span></td> 
>    <td style="vertical-align:middle;width:17pt;"><span style="color:#000000;">4</span></td> 
>    <td style="vertical-align:middle;width:17pt;"><span style="color:#000000;">5</span></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 假设有4块木板，此时最小的总长度是每个牛棚占据一个木板，最小总长度ans = 所占牛棚数c
> 
> （二）木板数少于所占牛棚数
> 
> 思路：可以从假设只有一个木板结果是什么，然后假设有两个木板，假设有3个木板。
> 
> 其实可以转化为在白色空格处分割m-1次的问题。
> 
> 1. 假设只有一个木板。
> 
> ans = a\[c\]-a\[1\]+1;
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1][]
> 
> 2. 假设有两个木板
> 
> 只需要从空白处隔开。
> 
> 怎么选择空白处呢？ （贪心）空白处最多的地方隔开，此时ans最小
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2][]
> 
> 因此，需要计算空白处的间隔，然后将空白处的间隔从大到小排序，然后ans每分割一次，减去最大的间隔即可。

/*
    ID: L
    PROG: barn1 
    LANG: C++ 
    */ 
    #include<bits/stdc++.h> 
    using namespace std;
    int a[205],b[205];
    bool cmp(int x,int y)
    {
    	return x > y;
    }
    int main()
    {
    	freopen("barn1.in","r",stdin);
    	freopen("barn1.out","w",stdout);
    	int m,s,c;
    	cin >> m >> s >> c;
    	for(int i = 1; i <= c; ++i)
    		cin >> a[i];
    	if(m >= c)//特判,当木板数大于所占牛棚数 
    	{
    		cout << c << endl;
    		return 0;
    	 } 
    	sort(a+1,a+1+c);//牛棚编号从小到大排序，题目不一定是从小到大排序的 
    	int ans = a[c]-a[1]+1;//ans:所需木板最小总长度，初始条件假设只有一个木板 
    	for(int i = 1; i < c; ++i)//间隔的空格数 
    		b[i] = a[i+1] - a[i];
    	sort(b+1,b+c,cmp);//间隔空格数从大到小排序 
    	for(int i = 1; i <= m-1; ++i)//分割m-1次，每次从最大间隙中分割 
    		ans = ans - b[i] + 1;	
    	cout << ans << endl;
    	fclose(stdin);
    	fclose(stdout);
    	return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1209
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20230528/1bbebd24481c4739b752cf7d93eeab9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1]: /images/20230528/ed8636125daf47d097f7fd01fa626933.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2]: /images/20230528/d005a234112a47868384254843047f64.png