题目|区间平均值（逆序对）
区间平均值 【题目|区间平均值（逆序对）】问题描述：
有N个数，随机选择一段区间，如果这段区间的所有数的平均值在[l, r]中则你比较厉害。求你比较厉害的概率。
输入格式：
第一行有三个数N, l, r，含义如上描述。
接下来一行有N个数代表每一个数的值。
输出格式：
输出一行一个分数a/b代表答案，其中a, b互质。 如果答案为整数则直接输出该整数即可。
样例输入 1：
4 2 3
3 1 2 4
样例输出 1：
7/10
样例输入 2：
4 1 4
3 1 2 4
样例输出 2：
1
样例解释：
塔外面有棵树。
数据规模与约定：
对于30%的数据， 1 ≤ N ≤ 104。
对于60%的数据， 1 ≤ N ≤ 105。
对于100%的数据， 1 ≤ N ≤ 5 × 105, 0 < l ≤ r ≤ 100。
思路：
要求 区间平均值>=l&&<=r 的个数
即
现在我们来求区间平均值在1~r的个数和1~l(不包括l)的个数 前减后即为所求
以求1~r为例
(a[i]+a[i+1]+……+a[i+k-1])/k<=r
(a[i]+a[i+1]+……+a[i+k-1])<=k*r
(a[i]+a[i+1]+……+a[i+k-1])-k*r<=0
(a[i]-r)+(a[i+1]-r)+……+(a[i+k-1]-r)<=0
令c[i]=a[i]-r得到一个新数组c
即求c数组区间和<=0的个数
令s为数组c的前缀和数组
c[i]+c[i+1]+…+c[i+k-1]<=0
s[i+k-1]-s[i]<=0
s[i+k-1]<=s[i]
则
i< i+k-1
s[i]>=s[i+k-1]
即求s数组逆序对数
#include
#include
#include
#include
#define lon long long
using namespace std;
const int maxn=500010;
lon n,l,r,ans1,ans2,a[maxn],b1[maxn],b2[maxn],c[maxn];
lon s1[maxn],s2[maxn];
lon lowbit(lon x)
{
return x&(-x);
}
void add(lon x)
{
for(lon i=x;
i<=n;
i+=lowbit(i))
c[i]++;
}
lon getsum(lon x)
{
lon ans=0;
for(lon i=x;
i>=1;
i-=lowbit(i))
ans+=c[i];
return ans;
}
int main()
{
freopen("jian.in","r",stdin);
freopen("jian.out","w",stdout);
cin>>n>>l>>r;
for(lon i=1;
i<=n;
i++)
scanf("%d",&a[i]);
for(lon i=1;
i<=n;
i++)
{
s1[i]=s1[i-1]+a[i]-l;
b1[i]=s1[i];
if(s1[i]<0) ans1++;
}
for(lon i=1;
i<=n;
i++)
{
s2[i]=s2[i-1]+a[i]-r;
b2[i]=s2[i];
if(s2[i]<=0) ans2++;
}
sort(s1+1,s1+n+1);
sort(s2+1,s2+n+1);
lon t1=unique(s1+1,s1+n+1)-s1-1;
lon t2=unique(s2+1,s2+n+1)-s2-1;
for(lon i=1;
i<=n;
i++)
{
lon pos=lower_bound(s1+1,s1+t1+1,b1[i])-s1;
b1[i]=pos;
pos=lower_bound(s2+1,s2+t2+1,b2[i])-s2;
b2[i]=pos;
}
for(lon i=n;
i>=1;
i--)
{
ans1+=getsum(b1[i]);
add(b1[i]+1);
}
memset(c,0,sizeof(c));
for(lon i=n;
i>=1;
i--)
{
ans2+=getsum(b2[i]);
add(b2[i]);
}
lon up=ans2-ans1;
lon down=n*(n+1)/2;
if(up%down==0)
cout< 推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- leetcode|leetcode 92. 反转链表 II
- 年国考行测备考（重要的题目做三遍）
- 【C】题目|【C语言】题集 of ⑥
- Leetcode|Leetcode No.198打家劫舍
- JS|JS 数组求和与数组求平均值
- 此生未完成
- 2019腾讯笔试题
- 进阶任务十四
- 分享几个前端面试题目