[USACO1.3] Repair Barn Repair
Title Description
On a dark and stormy night, the roof and doors of Farmer John's barn blew off Luckily, many of the cows were on vacation, so the barn wasn't full.
The cowsheds were lined up one next to the other and the cows lived in them overnight. Some of the barns had cows in them and some did not. All the cowsheds had the same width. The width was 1
Farmer John must put up new boards in front of the barn as soon as possible since the door was lost. His new lumber supplier will supply him with any length he wants, but the stingy supplier can only supply a limited number of boards. Farmer John wants to minimize the total length of the boards he buys.
give\(m,s,c\), indicating the maximum number of planks, the total number of barns, the total number of cows; and the number of the barn in which each cow is housed, calculate the minimum total length of planks required to stop all barns with cows.
input format
Three integers in a row\(m,s,c\), meaning as described in the title.
accept\(c\) rows, each containing an integer indicating the number of the barn occupied by the cow.
output format
Outputs a line with an integer indicating the minimum total length of boards required.
Sample #1
Sample Input #1
4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43
Sample Output #1
25
draw attention to sth.
[Data range]
with regards to\(100\%\) of the data.\(1\le m \le 50\)，\(1\le c \le s \le 200\)。
USACO Training Section 1.3
Thoughts:
- There is a lot of information in the question, let's first run through the meaning of the question. s is not relevant to the solution, we should eliminate useless information, the supplier can provide at most m boards, there are c barns with c cows living in them, we need to repair these c barns, each barn needs a board of length 1, but our total number of boards is not more than m, so when m < c, we need to use an extension of the boards for some barns be extended, e.g., for the two cowsheds numbered 2, 3, we use a board of length 2 to repair it until the total number of boards we use is equal to m.
- One way to think about this is to start by assigning a board of length 1 to each barn with cows; if the total number of boards supplied ≥ the number of cows, then our answer is c, and it is sufficient to assign a board of length 1 to each barn; otherwise, we will have to use consecutive boards to repair multiple barns. For example, for boards numbered 3 and 8, we use boards of length 6 to repair them, but since we started by assigning one board of length 1 to each barn, we only need to add 8-3-1 to our original answer, which is 4, so that means that we have to count how many barns are separated from each other.
- From the above idea, we have to make an array of barns with cowsaPerform sorting and use another arraydis used to denoteaThe number of bullpens separated by neighboring elements in the
- First sort the array of barns a and assign a board of length 1 to each barn:
for (int i = 1; i <= c; i++) cin >> a[i].
//First assign a plank to each barn with cows, and if the maximum number of planks is not enough, you have to
//connect certain planks together now.
int ans = c;
sort(a + 1, a + 1 + c).
- Then, we calculate the number of planks for the neighboring elements in a and sort the d array
for (int i = 2; i <= c; i++) d[i - 1] = a[i] - a[i - 1] - 1;
// the d array has a total of c - 1 elements
sort(d + 1, d + c);
- If m<c, we choose the smallest element in the d array each time, because the number of planks separating them is the lowest, the lower the cost of plank length we need to pay, which is the local optimal solution corresponding to the greedy idea. In the past, we must use the least length of planks, and finally get the global optimal solution.
Code:
#include<iostream>
using namespace std.
#include<algorithm>
int a[205]; //as the number of the barn with the cows
int d[205]; //as the number of stalls with cows between two neighboring stalls
int m, s, c; int main()
int main()
{
cin >> m >> s >> c.
for (int i = 1; i <= c; i++) cin >> a[i];
//first assign a plank to each barn with cows, if the maximum number of planks is not enough
//connect certain planks together now.
int ans = c;
sort(a + 1, a + 1 + c);
for (int i = 2; i <= c; i++) d[i - 1] = a[i] - a[i - 1] - 1;
sort(d + 1, d + c);
// If the maximum number of boards provided is less than the number of cows, at this point you can't assign boards to every barn with cows, you have to concatenate boards from certain barns.
if (m < c) {
//The d array has a total of c-m elements, since there are c cows, providing at most m boards
// We greedily choose the barns with the least number of cows apart each time, so that the lower our cost, the smaller the result we get.
for (int i = 1; i <= c - m; i++) ans += d[i];
}
cout << ans << endl.
return 0; }
}
Summary and reflections
- The most important ability for us to do informatics competitions is the ability to read useful information quickly and build our own models, or draw corresponding sketches, then perform the corresponding mathematical relationships on draft paper, and finally represent them in code.