Problem Analysis

The objective is to cover all occupied stalls in a linear arrangement using a maximum of M boards, minimizing the total length of the boards. If only one board is available, it must span from the leftmost occupied stall to the rightmost. Adding more boards allows leaving gaps between consecutive occupied stalls. To minimize the total length, the largest gaps should be excluded. With M boards, we can leave M-1 gaps. The optimal strategy is to identify the M-1 largest distances between consecutive cows and exclude them from the total span.

Key Pitfalls

• The input sequence of occupied stall indices is not guaranteed to be sorted. Sorting is a mandatory prerequisite before calculating distances.
• The number of available boards M can exceed the number of cows C. In this scenario, each cow can be covered by a separate board of length 1, resulting in a total length of C.

Algorithm Steps

1. Read the input values for maximum boards (M), total stalls (S), and number of cows (C), followed by the stall numbers.
2. Handle the edge case: if M is greater than or equal to C, output C and terminate.
3. Sort the occupied stall indices in ascending order.
4. Calculate the initial total length as the distance from the first cow to the last cow, plus 1 (inclusive counting).
5. Compute the gaps between consecutive cows. A gap between stall A and stall B is B - A - 1.
6. Sort these gaps in descending order.
7. Subtract the M-1 largest gaps from the initial total length.
8. Output the resulting minimum length.

Code Implementation

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int max_boards, total_stalls, num_cows;
    std::cin >> max_boards >> total_stalls >> num_cows;

    std::vector<int> positions(num_cows);
    for (int i = 0; i < num_cows; ++i) {
        std::cin >> positions[i];
    }

    if (max_boards >= num_cows) {
        std::cout << num_cows << "\n";
        return 0;
    }

    std::sort(positions.begin(), positions.end());

    int initial_span = positions.back() - positions.front() + 1;

    std::vector<int> gaps;
    for (int i = 1; i < num_cows; ++i) {
        int current_gap = positions[i] - positions[i - 1] - 1;
        if (current_gap > 0) {
            gaps.push_back(current_gap);
        }
    }

    std::sort(gaps.rbegin(), gaps.rend());

    int result = initial_span;
    for (int i = 0; i < max_boards - 1 && i < static_cast<int>(gaps.size()); ++i) {
        result -= gaps[i];
    }

    std::cout << result << "\n";

    return 0;
}