题目描述
blablabla
样例
blablabla
解题思路:
差分 + 暴力枚举,范围1000,维护一个差分数组。对于每一个灯,我们让a[x - k] + +, a[x + k + 1] - -。
再对差分数组做一遍前缀和,那么0的部分就是没有被照亮的部分,我们只需要统计连续0的长度,然后向上取整即可。
照亮的长度 P = 2 * k + 1, 那么该区域需要灯的数量为:ceil(len / p) 输出res即可。
时间复杂度O(n)
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, k;
int a[N];
int main() {
while (cin >> n >> m >> k) {
memset(a, 0, sizeof a);
for (int i = 1; i <= m; i ++) {
int x;
cin >> x;
a[max(1, x - k)] ++, a[x + k + 1] --;
}
for (int i = 1; i <= n; i ++) a[i] += a[i - 1];
int res = 0, p = 2 * k + 1;//P为照亮的最大长度
for (int i = 1; i <= n; i ++) {
int len = 0;
while (!a[i] && i <= n) {//求连续的0的区间长度
len ++;
i ++;
}
if (len) res += ceil((double)len / p);
}
cout << res << endl;
}
return 0;
}