P2717 寒假作业

题目传送门

题目背景

zzs 和 zzy 正在被寒假作业折磨，然而他们有答案可以抄啊。

题目描述

他们共有 $n$ 项寒假作业。zzy 给每项寒假作业都定义了一个疲劳值 $a$，表示抄这个作业所要花的精力。

zzs 现在想要知道，有多少组连续的寒假作业的疲劳值的平均值不小于 $k$？

简单地说，给定一个长度为 $n$ 的正整数序列 { a i } \{a_i\} {ai​}，求出有多少个连续子序列的平均值不小于 $k$。

输入格式

第一行是两个整数，分别表示序列长度 $n$ 和给定的参数 $k$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

3 2
1
2
3

样例输出 #1

4

提示

样例 1 解释

共有 $6$ 个连续的子序列，分别是 $(1)$、$(2)$、$(3)$、$(1,2)$、$(2,3)$、$(1,2,3)$，平均值分别为 $1$、$2$、$3$、$1.5$、$2.5$、$2$，其中平均值不小于 $2$ 的共有 $4$ 个。

数据规模与约定

• 对于 $20\%$ 的数据，保证 $n\le 100$。
• 对于 $50\%$ 的数据，保证 $n\le 5000$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$1\le a_i,k\le 10^4$。

思路

我们把题意简化一下，就是求一个区间 $[l,r]$ 满足 $\frac{{\sum }_{i=l}^r}{r-l+1}\ge k$ 的数量。

我们可以推理一下：

首先我们如果把 $a$ 数组全部减 $k$ 那么上述式子就变成了：$\frac{{\sum }_{i=l}^r}{r-l+1}\ge 0$

即：${\sum }_{i=l}^r\ge 0$

设 $s$ 表示 $a$ 数组的前缀和。

带入上述式子：$s_r-s_{l-1}\ge 0$

到这里题目就已经转换成了：求 $i,j(1\le i<j\le n)$ 满足 : $s_j\ge s_i$ 的数量

也就是求 $s$ 数组的顺序对的数量：

可以用归并排序或者树状数组来求。

不会归并排序的可以看这个

code

#include <bits/stdc++.h>
#define LL long long 
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const int N = 1e5 + 5;
int a[N] , s[N] , n , k;
LL ans;
int read () {int val = 0 , fu = 1;char ch = getchar ();while (ch < '0' || ch > '9') {if (ch == '-') fu = -1;ch = getchar ();}while (ch >= '0' && ch <= '9') {val = val * 10 + (ch - '0');ch = getchar ();}return val * fu;
}
void gb(int l , int r) {if (l == r) return;else {int mid = l + r >> 1;gb (l , mid);gb (mid + 1 , r);fu (i , l , r) a[i] = s[i];int i = l , j = mid + 1 , sum = l;while (i <= mid && j <= r) {if (a[i] <= a[j]) {ans += r - j + 1;s[sum ++] = a[i ++];}elses[sum ++] = a[j ++];}while (i <= mid) s[sum ++] = a[i ++];while (j <= r) s[sum ++] = a[j ++];}
}
int main () {n = read () , k = read ();fu (i , 1 , n) {a[i] = read ();a[i] -= k;}fu (i , 1 , n) s[i] = s[i - 1] + a[i];fu (i , 1 , n) ans += (s[i] >= 0);gb (1 , n);printf ("%lld" , ans);return 0;
}