平均数

【问题描述】
有一天,小A得到了一个长度为n的序列。
他把这个序列的所有连续子序列都列了出来, 并对每一个子序列都求了其平均值, 然后他把这些平均值写在纸上, 并对它们进行排序,最后他报出了第k小的平均值。
你要做的就是模仿他的过程。

【输入格式】
第一行两个整数n,k,意义如题中所述。
第二行n 个正整数,即为小A 得到的序列。

【输出格式】
一行一个实数,表示第k小的平均值,保留到小数点后4位。

【样例输入输出】
ave.in
6 10
3 5 4 6 1 2

ave.out
3.6667

【数据范围与约定】
对于40%的数据,n≤1000
对于100%的数据,n≤100000,k≤n*(n+1)/2,序列中的数≤10^9

分析:
二分答案,
然后判断二分的结果是不是恰好为第k位
记当前二分答案为mid
首先统计出每一个元素和mid的差值,记为d[i],
对于区间[l,r],如果d[l]~d[r]之和要大于0,
那么这段区间的平均值就一定要大于二分的答案
那么如何快速求区间和呢
当然是前缀和啦
于是考虑求出前缀和,记为sum[i],
那么区间[l,r]的答案就是sum[r]-sum[l-1],
即有多少对sumd[r]-sumd[l-1]<0即为答案
喜闻乐见的求逆序对个数,
树状数组即可,加上二分时间复杂度就是O(nlog^2n)

由于运用树状数组的常数要大一点,最后几个点时间已经退化到了>0.9

需要注意的是,在计算逆序对的时候,
第一个元素造成的逆序对也需要计算
(说白了就是若第一个元素和mid的差<0,那么逆序对个数++)
一开始一直wa4个点,后来才知道,
在计算逆序对个数时,数量累计器ans也要开long long
(仔细算一下发现,确实是,100000*100000/2铁定爆int啊,我大概是个zz)
最后在输出时要输出
右端点/100000
输出 左端点/N 就会WA一个点 ,这也许就是四舍五入的力量吧

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

int n,m;
const int N=100000;
ll mx=0,mn=10000000000005;
struct node{
    ll sum;
    int id;
} d[100001];
ll v[100001];
int cc[100001];

ll max(ll a,ll b)
{
    if (a>b) return a;
    else return b;
}

ll min(ll a,ll b)
{
    if (a<b) return a;
    else return b;
}

int cmp(const node &a,const node &b)
{
    return a.sum<b.sum;
}

void add(int x)
{
    for (int i=x;i<=n;i+=i&(-i))
        cc[i]++;
}

ll ask(int x)
{
    int tot=0;
    for (int i=x;i>=1;i-=i&(-i))
        tot+=cc[i];
    return tot;
}

ll pd(ll x)
{
    int i,j;
    ll ans=0;
    d[1].sum=0;  //第一位本身的逆序对也需要计算上 
    d[1].id=1;   //所以序列的第一位赋成0 
    for (i=1;i<=n;i++)
    {
        ll f=v[i]-x;  //差值
        d[i+1].sum=d[i].sum+f;   //前缀和 
        d[i+1].id=i+1;
    }
    sort(d+1,d+1+n+1,cmp);
    for (i=1;i<=n+1;i++) cc[i]=0;
    for (i=1;i<=n+1;i++)
    {   //按排列顺序从小到大添加,在树状数组中的位置是n-x+1 
        add(n+1-d[i].id+1);
        ans+=ask(n+1-d[i].id);
    }
    return ans;
}

void doit()
{
    ll l=mn;
    ll r=mx;
    while (r-l>1)
    {
        ll mid=(l+r)/2;
        if (pd(mid)>=m)
            r=mid;
        else l=mid;
    }
    printf("%0.4lf",(double)r/(double)N);  //不知道为什么要输出r/N 
}   //然而输出l/N就会WA一个点 ,这也许就是四舍五入的力量 

int main()
{
    freopen("ave.in","r",stdin);  
    freopen("ave.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&v[i]);
        v[i]*=N;
        mx=max(mx,v[i]);
        mn=min(mn,v[i]);
    }   
    doit();
    return 0;
} 
原文地址:https://www.cnblogs.com/wutongtong3117/p/7673522.html