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

· · 题解

为表述方便，题目中的小时在本文中用“次”表示。

显然，为了让修剪次数尽可能少，我们应该让每次修剪的区间尽可能不相交。然而这样的话，可能会剩下一些草坪没有修剪，这时候我们就需要再修剪一次。为了只再修剪一次，我们应该让没有修剪的部分集中在一起。

因此，可以得到次数为 \lfloor\frac{n}{k}\rfloor 次，如果最后还剩下一些没有修剪（n\bmod k\neq0）那么就是 \lfloor\frac{n}{k}\rfloor+1，合起来得到公式为 \lceil\frac{n}{k}\rceil。

但如果这样你交上去只能得 76 分，问题就出在

该子段完全被草覆盖

这一句不起眼的话上。

我们举一个例子：n=3,k=2。按照我们刚才推的公式，修剪次数应该是 2，乍一看也没啥问题，但如果第一次修剪了 [1,2] 区间的草坪，那么第二次就没法再修剪 [2,3] 区间的草坪了，因为 [2,2] 区间没有被草覆盖，我们只能等着，等到第三次再修剪 [2,3]。

但这种情况只在剪一次就没法再剪了的时候出现，比如 n=5,k=2，我们可以先剪 [3,4] 区间，再剪 [1,2] 区间，这时候 [3,4] 区间又长好了，再剪 [4,5]。

所以第一种情况的公式不变，但只适用于剪了第一次还能再剪至少一次，或恰好需要剪一次时。第二种情况由于只在剪一次就没法再剪了的时候出现，所以只需要剪一次，等一次，再剪一次，直接输出 3。注意第二种情况要求剪一次后还有需要剪的，也就是 n\bmod k\neq0。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ft first
#define sd second
#define fs(i,x,y) for(int i=(x);i<=(y);i++)
#define fj(i,x,y) for(int i=(x);i>=(y);i--)
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    if(n/k==1&&n%k!=0)cout<<3;
    else cout<<ceil(n*1.0/k);
    return 0;
}

结尾

数学题就是这样，讲着费劲，但写代码简单。