题目: X学校被抽中进行一次数学测验,该学校共有N人,每个人有一个学号,一号学生的学号是1...N号学生的学号是N.
为了减轻统计的负担,该学校只会随机抽取学号连续的k人(1≤k≤n),且将该k人的平均分统计出来。小明已经知道了所有人的成绩,小明想知道,平均分在[L,R]上的概率为多少。
【数据范围】
对于30%的数据,N≤10,000
对于100%的数据,N≤1,000,000。
没错,它绿了;
分析:
如果直接暴力用区间枚举,即使用前缀和优化,复杂度依然是O(N^2),会超时。但如果尝试以下数学推理,问题会发生微妙的变化:
L <= (sum[i]-sum[j]) / (i-j) <= R ===> tot;(数目)
L <= (sum[i]-sum[j]) / (i-j) ===> L*i-sum[i] <= L*j-sum[j] ===> ans1;(数目)
R < (sum[i]-sum[j]) / (i-j) ===> R*i-sum[i] < R*j-sum[j] ===> ans2;(数目)
易得:tot = ans1-ans2;
注意红色的部分,可以发现他们可以经过专门处理而变成新的数组A,B,接下来我们要做的就是去求数组中的逆序对了。
求逆序对有三种思路:
线段树,树状数组,归并排序;
因为此题中对于L 和 R ,逆序对分别可以和不可以取等,所以用树状数组不好处理,所以只好用归并排序。
注意:当红色的式子中j取1时,需要A[0]和B[0],因此A[0]和B[0]也是序列中的一部分(虽然是0),它蕴含着所有包含1的逆序对的信息,因此算逆序对时要从(0,N)开始。
下面是参考代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
long long a[1000010],sum[1000010],tot=0;
long long n,L,R;
bool flag=1;
long long AA[1000010],BB[1000010];
long long temp[1000010]={0};
void mergesort(long long l,long long r,long long f[])
{
if(l==r) return;
long long mid=(l+r)/2;
mergesort(l,mid,f);
mergesort(mid+1,r,f);
long long i=l,p=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(f[i]>f[j] || (f[i]==f[j])*flag)
{
temp[p++]=f[j++];
tot+=mid-i+1;
}
else
temp[p++]=f[i++];
}
while(i<=mid) temp[p++]=f[i++];
while(j<=r) temp[p++]=f[j++];
for(int i=l;i<=r;i++)
f[i]=temp[i];
}
long long gcd(long long x,long long y)
{
while(x)
{
int temp=y%x;
y=x;
x=temp;
}
return y;
}
int main()
{
cin>>n>>L>>R;
for(long long i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(long long i=0;i<=n;i++)
{
AA[i]=L*i-sum[i];
BB[i]=R*i-sum[i];
}
long long ans1=0,ans2=0;
mergesort(0,n,AA);
ans1=tot,tot=0;
flag=0;
mergesort(0,n,BB);
ans2=tot;
tot=ans1-ans2;
long long cnt=n*(n+1)/2;
if(cnt==tot)
cout<<1;
else if(tot==0)
cout<<0;
else
{
long long tt=gcd(tot,cnt);
printf("%lld/%lld",tot/tt,cnt/tt);
}
return 0;
}
View Code
转载于:https://www.cnblogs.com/linda-fcj/p/7206236.html