不会就问：请问这道题怎么做？

Question

C++语言

已知一个长度=N的数组a和一个整数K，请问在这些子段中，有多少个子段的平均值>=K。

本人想的是O(n^2)的算法，但是N<=10^6，有没有好的方法？

Answer 1

提供一个思路(没有代码,完善太耗费时间了)：（递归）
一、初步思路
设1：N=100
设2：变量int nCount = 0; //nCount用于计数平均值>=K的字段。
设3：N个元素和为total

当N=100时，
1.100个元素的平均值是否大于K（即等同于total和100K的比较）。
if(total>=100k) //其他条件不计数
nCount++;

2.100个元素剔除任意一个元素（即a[i],for循环遍历100次），剩余下的99个平均值是否大于K（即是根据 a[i]-K和total-100K的关系 判断是否执行 nCount++）。
if( a[i]-K <= total-100K ) //**根据减少的程度来判断**
nCount++

3.更新total=total-a[i] ,N = N-1

二、递归核心思想
100个元素，剔除任意一个，for循环遍历100次完成后，递归1次完成
99个元素，剔除任意一个，for循环遍历100次完成后，递归2次完成
98个元素，剔除任意一个，递归遍历98次for循环遍历100次完成后，递归3次完成
x个元素，剔除任意一个，递归遍历x次for循环遍历x次完成后，递归N-x次完成