更好的阅读体验
题意
实现一个函数,求在一个 \(N \times M\) 的矩阵中放置最少炮塔数的方案,使得每个 \(K \times K\) 的正方形区域内至少有一个炮塔。
思路
观察样例可以发现,在最优情况下 每行每隔 \(K-1\) 格就有一个炮塔,再看列也是如此,所以 $ans = \left \lceil \frac{N-K+1}{K} \right \rceil \times \left \lceil \frac{M-K+1}{K} \right \rceil $
通过这个回答
可以知道 \(\left \lceil \frac{x}{n} \right \rceil = \left \lfloor\frac{x-n+1}{n} \right \rfloor\) 反之可以得到 \(\left \lfloor \frac{x}{n} \right \rfloor = \left \lceil \frac{x+n-1}{n} \right \rceil
即\left \lfloor \frac{N}{K} \right \rfloor = \left \lceil \frac{N+K-1}{K} \right \rceil\)
所以 \(ans = \left \lfloor \frac{N}{K} \right \rfloor \times \left \lfloor \frac{M}{K} \right \rfloor\)
代码
此题是交互题,只需要把所写函数交上去即可
//C++ "优化"前
#include<bits/stdc++.h>
using namespace std;
int solve(int N, int M, int K){return ceil(((N-K+1.0)/(K*1.0)))*ceil(((M-K+1.0)/(K*1.0)));
}
//C++ "优化"后
int solve(int N, int M, int K){return (N/K) * (M/K);
}
话说优化前比优化后运行还快?