#include<bits/stdc++.h> using namespace std; long long a[100001],s[100001]; bool cmp(long long x,long long y){ return x>y; } int main(){ long long n,k,ans=0,j; cin>>n>>k; j=n; for(int i=1;i<=n;i++){ cin>>a[i]; a[i]-=k; } int mid=(n+1)/2; for(int i=1;i<=mid;i++) s[i]=s[i+1]+a[i]; for(int i=mid+1;i<=n;i++) s[i]=s[i-1]+a[i]; sort(s+1,s+mid+1,cmp); sort(s+mid+1,s+n+1); for(int i=1;i<=mid;i++){ while(j>mid&&s[i]+s[j]>=0) j--; ans+=(n-j); } cout<<ans; }

这题是洛谷P2717的弱化版，也是前缀和优化题

假设有一个满足条件的子序列在 $[a_l,a_r]$ 间，显然，一共有 $r-l+1$ 个数字，由于这些数的平均数大于等于 $k$ 即：

$a_l+a_{l+1}+.......+a_{r-1}+a_r≥(r-l+1) \times k$

稍稍亿一变形可得

$a_l+a_{l+1}+.......+a_{r-1}+a_r-(r-l+1) \times k≥0$

$(a_l-k)+(a_{l+1}-k)+.......+(a_{r-1}-k)+(a_r-k)≥0$

所以我们可以在输入时对每个 $a_i$ 减 $k$，在查找时直接判断是否大于0即可

再看前缀和优化部分，假设我们挑选了这样一个子序列：

$a_1, a_2, ... , a_l, a_{l+1}, ... , a_{mid} , ... , a_{r-1}, a_r, ...$

显然 $[a_l,a_{mid}]$ 部分的和相当于 $a_l$ 的后缀和，而 $[a_{mid+1},a_r]$ 部分的和相当于从 $a_{mid+1}$ 开始，到 $a_r$ 的前缀和

注意：从 $a_ {mid+1}$ ​开始！！！！！

因为序列是分为两部分的，如果从 $a_1$ 开始，必然会把 $[a_1, a_{mid}]$ 的部分多余算

但你以为这就完了么？

实际上手还会超时的！！！

这就意味着我们得继续减复杂度

毕竟是前缀和，我们只需要看区间和满足不满足要求，调换顺序不影响。所以可以通过排序来减少多余的区间计算

我们可以将 $[a_1, a_{mid}]$ 的部分从大到小排，剩下的部分从小到大排，再用双指针扫一遍，结束！

上代码：

#include<bits/stdc++.h>
using namespace std;
long long a[100001],s[100001];
bool cmp(long long x,long long y){
	return x>y;
}
int main(){
	long long n,k,ans=0,j;
	cin>>n>>k;
	j=n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]-=k;
	}
	int mid=(n+1)/2;
	for(int i=1;i<=mid;i++) s[i]=s[i+1]+a[i];
	for(int i=mid+1;i<=n;i++) s[i]=s[i-1]+a[i];
	sort(s+1,s+mid+1,cmp);
	sort(s+mid+1,s+n+1);
	for(int i=1;i<=mid;i++){
		while(j>mid&&s[i]+s[j]>=0) j--;
		ans+=(n-j);
	}
	cout<<ans;
}