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

z10702 · 2026-01-24 15:55:23 · 题解

P15007。

题意

有一块长度为 n 米、宽度为 1 米的草坪。
每小时可以选择一个长度为 k 米的连续段进行修剪（该段必须全部有草）。
修剪后的一整小时，被修剪的区域会瞬间重新长满草，我们要让草坪的每个位置都至少被修剪过一次。
求最少需要多少小时。

思路

由于修剪后草会重新生长，所以我们在某一小时内修剪的区间集合要覆盖整个草坪。

但是每小时只能修剪一个长度为 k 的区间，所以一小时内最多只能覆盖 k 米。

实现

我们需要安排若干小时的修剪计划，使得存在某个时刻，所有位置都已被修剪过（不要求同时保持修剪状态）。

相当于用若干个长度为 k 的区间覆盖 [1, n] 的所有整数点，求最少区间数（因为每小时一个区间）。

设最少区间数为 m = \lceil n/k \rceil。

特判

1. 当 n = k 时
   一次就可以完成，输出 1。

2. 当 n \le 2k-1 且 n > k 时
   这个时候 m = 2，但两个长度为 k 的区间最多覆盖 2k 米，它们必须有重叠。
   因为 n \le 2k-1，这两个区间的中间部分可能无法完全覆盖（例如 n=5, k=3，会漏掉位置 4）。
   所以需要第三个区间来填补空隙，输出 m+1。

3. 当 n > 2k-1 时
   此时可以用 m 个区间像铺砖一样覆盖，相邻区间适当重叠就可以保证无遗漏，输出 m。

代码

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