题意

给定长度为$n$的整数数组$a$，进行$m$次询问。每次询问给出一个整数$k$，求有多少个区间 $[i,j]$ 满足该子数组的平均值小于等于$k$。

50pts

思路

枚举所有子区间，计算其平均值，判断是否满足条件。

时间复杂度

$O(mn^2)$

代码

#include<bits/stdc++.h>
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int rd(){
	int x=0,f=1;char c=gc();
	for(;c<'0'||'9'<c;c=gc()) if(c=='-') f=-1;
	for(;'0'<=c&&c<='9';c=gc()) x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
const int MAXN=100010;
int a[MAXN];
long long s[MAXN];
int main(){
	int n=rd();
	for(int i=1;i<=n;++i){
		a[i]=rd();
		s[i]=s[i-1]+a[i];
	}
	int m=rd();
	while(m--){
		int k=rd();
		long long ans=0;
		for(int i=1;i<=n;++i){
			for(int j=i;j<=n;++j){
				if(s[j]-s[i-1] <= 1LL*k*(j-i+1))//不乘1LL会得0pts  QwQ
					ans++;
			}
		}
		printf("%lld\n",ans);
	}
    return 0;
}

100pts

$\frac{s[j]-s[i-1]}{j-i+1} \le k$
两边同乘正数 $(j-i+1)$
$s[j]-s[i-1] \le k\cdot(j-i+1)$
移项得：
$\boldsymbol{s[j] - k\cdot j \le s[i-1] - k\cdot (i-1)}$
令数组 $b[x] = s[x] - k \cdot x$
原问题等价于：
求满足 $\boldsymbol{0 \le x < y \le n}$ 且 $\boldsymbol{b[y] \le b[x]}$ 的数对数量。
就是求数组 b 的「逆序对」数量。

代码(用归并求的逆序对）

#include<bits/stdc++.h>
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int rd(){
	int x=0,f=1;char c=gc();
	for(;c<'0'||'9'<c;c=gc()) if(c=='-') f=-1;
	for(;'0'<=c&&c<='9';c=gc()) x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
const int MAXN=100010;
long long a[MAXN],s[MAXN];
long long b[MAXN],tp[MAXN]; 
int n,m;
long long ans;
void merge(int l,int r){
    if(l>=r) return;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int i=l,j=mid+1,p=l;
    while(i<=mid && j<=r){
        if(b[i]>=b[j]){
            ans+=mid-i+1; // 统计逆序对
            tp[p++]=b[j++];
        }else{
            tp[p++]=b[i++];
        }
    }
    while(i<=mid) tp[p++]=b[i++];
    while(j<=r) tp[p++]=b[j++];
    for(int k=l;k<=r;++k) b[k]=tp[k];
}

int main(){
	n=rd();
	for(int i=1;i<=n;++i){
		a[i]=rd();
		s[i]=s[i-1]+a[i];
	}
	m=rd();
	while(m--){
		long long k=rd();
		for(int i=0;i<=n;++i)
			b[i]=s[i]-k*i;
		ans=0;
		merge(0,n);
		printf("%lld\n",ans);
	}
    return 0;
}