题解：P15007 [UOI 2019 II Stage] 草坪

· · 题解

分析

我们有一个长度为 n 米的草坪，每次可以修剪一个长度为 k 米的连续子段（要求该子段完全被草覆盖）修剪需要 1 小时。在操作结束一小时后，该子段的草会重新生长出来。

目标是使得草坪的每个部分至少被修剪过一次，求所需的最短时间。

思路

最小区间覆盖

问题等价于用最少的长度为 k 的线段覆盖 n 个点，即答案为 \lfloor \frac{n}{k} \rfloor，事实上也符合样例。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    cout<<(n+k-1)/k;
    return 0;
}

拿到了 76\text{pts}。

问题：如果两次修剪的区间有重叠，那么第二次修剪必须等到第一次修剪后才能进行，否则第二次修剪时重叠部分还没有草。

考虑重新生长的影响

如果两次修剪的区间没有重叠，那么它们可以连续进行（后一次在前一次结束后立即开始）。

如果两次修剪的区间有重叠，那么后一次修剪必须在前一次修剪结束至少1小时后才能开始（因为草需要时间重新生长）。由于每次修剪耗时1小时，这意味着两次修剪的开始时间至少相差2小时。

那么只需选择若干个长度为 k 的区间，覆盖所有 n 个位置，并给这些区间安排一个顺序和开始时间，使得对于任意两个有重叠的区间，它们的开始时间之差至少为 2。

设使用了 m 个区间。

如果我们可以将这些区间排列成一个序列，使得序列中相邻的区间都没有重叠，那么这些区间就可以连续进行，总时间就是 m 小时。

因此，我们希望使用最少的区间数 m = \lfloor \frac{n}{k} \rfloor，如果存在这样的排列，答案就是 m，否则需要增加时间。

当 m = 1（即 n = k）时，显然只需要 1 小时。

当 m = 2 时，我们需要两个长度为 k 的区间覆盖 n 个位置。由于 m = \lfloor \frac{n}{k} \rfloor = 2，有 k < n \le 2k。

  1. 如果 n = 2k，我们可以选择两个互不重叠的区间（如 [1, k] 和 [k+1, 2k]），连续进行，总时间为2小时。

  2. 如果 n < 2k，则两个区间必然重叠，且无法避免相邻重叠（因为只有两个区间），因此总时间为 2 + 1 = 3 小时（第一个区间1小时，等待1小时让草重新生长，第二个区间1小时）。

当 m \ge 3 时，我们总可以构造一组区间，并排列它们使得相邻区间都不重叠，因此总时间为 m 小时。

那么有普遍规律：若 m = 1，答案为 1；若 m = 2 且 n < 2k，答案为 3；否则，答案为 m。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int m=(n+k-1)/k;
    if(m==1)cout<<1;
    else if(m==2&&n<2*k)cout<<3;
    else cout<<m;
    return 0;
}