USACO Section 1.3.2 [Barn Repair] Java题解
程序员文章站
2022-07-12 16:19:48
...
题意分析：
C头奶牛在畜栏里（一个畜栏里最多只能有一头奶牛），畜栏共有S个，并告诉你哪些编号的畜栏里有奶牛。一共有M块板要将所有有奶牛的畜栏栏起来。因为奶牛分布的分散和板的数量的限制，势必有空着的畜栏也被栏起来。求所有被栏起来的畜栏的最小个数。
解题思路：
比上一题稍难的贪心法。题目分析清楚后，S个畜栏这个条件实际上在计算中是没用的。为了使被栏起来畜栏数目最小，即空着被栏起来的畜栏最少，那么就要尽量减少横跨两个有牛畜栏间连续无牛畜栏的个数。这题贪心的思路就是将两个有牛畜栏间连续无牛畜栏个数进行排序，也就是碰到最大的M-1个连续无牛畜栏时，多用一块板以避免覆盖到这些无牛畜栏。剩余较小的连续无牛畜栏则必须被计算进去，再加上C个有牛畜栏则为输出。
代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/barn1.java
C头奶牛在畜栏里（一个畜栏里最多只能有一头奶牛），畜栏共有S个，并告诉你哪些编号的畜栏里有奶牛。一共有M块板要将所有有奶牛的畜栏栏起来。因为奶牛分布的分散和板的数量的限制，势必有空着的畜栏也被栏起来。求所有被栏起来的畜栏的最小个数。
解题思路：
比上一题稍难的贪心法。题目分析清楚后，S个畜栏这个条件实际上在计算中是没用的。为了使被栏起来畜栏数目最小，即空着被栏起来的畜栏最少，那么就要尽量减少横跨两个有牛畜栏间连续无牛畜栏的个数。这题贪心的思路就是将两个有牛畜栏间连续无牛畜栏个数进行排序，也就是碰到最大的M-1个连续无牛畜栏时，多用一块板以避免覆盖到这些无牛畜栏。剩余较小的连续无牛畜栏则必须被计算进去，再加上C个有牛畜栏则为输出。
代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/barn1.java