洛谷 P2717 寒假作业
https://www.luogu.org/problemnew/show/P2717
$n \le 1004枚举区间,挨个计算,判断,时间复杂度$O(n^3)$。
$n \le 5000$,预处理出一个前缀和,然后枚举区间,时间复杂度$O(n^2)$
#include50分代码#include #include #include #include #include using namespace std; #define LL long long LL a[100006],sum[100006],ans,k; int n; int main() { scanf("%d%lld",&n,&k); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { if((sum[i]-sum[j-1])/(i-j+1)>=k)ans++; } } printf("%lld",ans); }
对于100%的数据的话,我们首先计算平均值k嘛,我们把整个序列减去k,然后我们想,如果一段区间的和为整数那么这段区间的平均值就大于0,枚举区间是不可能了,但是前缀和依旧是个好东西啊,我们统计一下前缀和(减去k了哦),当这一段区间$[i,j]$的和大于0时那么$sum[j]>sum[i]$,所以我们要求的就是有多少对$(i,j)$,$i < j并且sum[i]#include