海南某神秘211校赛题 小飞飞刀

本题传送门

解题思路

既然要算一段区间的和，就用前缀和。

然后遍历这个数轴，如果一段窗口区间的前缀和爆了，就说明这个窗口最后一个元素加进来之后会超大小，根据题目，我们理论上可以把这个数修改成无穷小，然后所有包含这个数的区间都不用看了，以窗口大小为3举例很容易推导出参数表达。

ac✅️代码

#include<iostream>
using namespace std;
long long a[1000010];
long long sum[1000010];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n,m,k;
    cin>>n>>m>>k;
    
    for(int i = 1 ; i <= n ; i++)
    {
        cin>>a[i];    
    }
     
    for(int i = 1 ; i <= n ; i++)
    {
    	sum[i] = sum[i-1] + a[i];    
    }
    
    int cnt = 0 ;
    
    for(int i = m ; i <= n ; i++)
    {
		if(sum[i] - sum[i-m] >= k)
		{
			cnt ++;
			i += m - 1;
		}
		
	}
    
    
    cout<<cnt<<endl;
    return 0;
}