C++ 解法, 执行用时: 10ms, 内存消耗: 1832KB, 提交时间: 2020-07-10

/*思想：本题用了差分数组的思想，原来对于一个数组中我们想给[i,j]区间的每一个元素进行加1操作，一个个操作很耗时
，有了差分数组，我们只需要在i处加1，在j+1处减去1即可，最后通过差分数组就可以还原原数组！
差分数组：对于数组[a1,a2,a3,a4...],其差分数组[a1,a2-a1,a3-a2,a4-a3...]。第i项的值等于查分数组前i项的和。*/
#include<iostream>
#include<algorithm>
using namespace std;
long long const a = 0;
const int MAXSIZE = 1e5+2;

int main()
{
    ios::sync_with_stdio(false);
    long long n, k;
    cin >> n >> k;
    long long chafen[MAXSIZE] = {0};
    long long temp;
    for (long long i=0; i<n; i++)
    {
        cin >> temp;
        chafen[max(a, i-temp)]++; // 信号辐射的左边界
        chafen[min(n, i+temp+1)]--; // 信号辐射的右边界
    }
    int sum = 0, res = 0;
    for(long long i = 0; i<n; i++)
    {
        sum = sum + chafen[i];
        if (sum >= k)
        {
            res++;
        }
    }
    cout << res;
    return 0;
}

C++14 解法, 执行用时: 11ms, 内存消耗: 1372KB, 提交时间: 2020-08-20

#define faster ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include <iostream>
#include <algorithm>
using namespace std;


int n, k;
int nums[100001];

//法一：先处理一遍所有路由器的信号左右临界点，再从左到右遍历一遍每个位置的情况。类似leetc_253：会议室 解法
//时间复杂度：O(n)
int main()
{
	faster;
	cin >> n >> k;
	int len;
	for (int i = 0; i < n; ++i)
	{
		cin >> len;
		++nums[max(0, i - len)];     //意思是i-len的位置开始，多了一台路由器可以辐射
		--nums[min(i + len + 1, n)]; //意思是i+len+1的位置开始，少了一台路由器可以辐射
	}

	int num = 0;
	int count = 0;
	for (int i = 0; i < n; ++i)
	{
		num += nums[i];
		if (num >= k)
			++count;
	}

	cout << count;
	return 0;
}