ACM模版

描述

题解

二分答案，数据结构用树状数组比较好，期间需要离散化一下下。这里给了 4s 时限，有些多了，应该是需要注意一下输入优化的。

这里我们先求一下前缀和 sum[] 和最大值 mx ，然后二分，核心是 check() ，需要用到树状数组 + 离散化。

至于树状数组用来处理什么呢？我们可以推出如下：
二分过程我们需要 check(m) ，所以需要求有 x 区间的平均数大于等于 m ，而每一个区间 [i+1, j] 的平均数是 sum[j] − sum[i]j − i ，所以呢，

sum[j]−sum[i]≥m∗j−m∗i
sum[j]−m∗j−(sum[i]−m∗i)≥0
自然，我们需要考虑的实际上就是每个 sum[i]−m∗i ，但是这个值需要排序后进行离散化，接着就是对离散化后的这个序列进行树状数组处理，枚举右区间，查找符合要求的左区间数，然后逐个添加已经枚举过的右区间，作为左区间以备再次查找使用。

这个题简直就是为树状数组而设计的题，完美的利用了树状数组的功能。好题！

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 5;
const double ESP = 1e-5;

struct note
{
    double val;
    int pos;
} a[MAXN];

bool cmp(note a, note b)
{
    return a.val < b.val;
}

inline int lowbit(int t)
{
    return t & (-t);
}

int n;
ll k;
ll sum[MAXN];
int dct[MAXN];
int t[MAXN];

void add(int x)
{
    for (; x <= n; x += lowbit(x))
    {
        t[x]++;
    }
}

ll find(int x)
{
    ll ans = 0;
    for (; x; x -= lowbit(x))
    {
        ans += t[x];
    }

    return ans;
}

bool check(double m)
{
    a[0].val = a[0].pos = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i].val = sum[i] - m * i;
        a[i].pos = i;
    }
    sort(a, a + n + 1, cmp);

    int cnt = 0;
    ll x = 0;
    // discretize
    for (int i = 0; i <= n; i++)
    {
        if (!i || a[i].val != a[i - 1].val)
        {
            cnt++;
        }
        dct[a[i].pos] = cnt;
    }

    memset(t, 0, sizeof(t));
    add(dct[0]);
    for (int i = 1; i <= n; i++)
    {
        x += find(dct[i]);
        add(dct[i]);
    }
    if (x >= k)
    {
        return 1;
    }
    return 0;
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    scan_d(n), scan_d(k);

    ll mx = 0;
    for (int i = 1; i <= n; i++)
    {
        scan_d(sum[i]);
        mx = max(mx, sum[i]);
        sum[i] += sum[i - 1];
    }

    double l = 0, r = mx, m;
    while (r - l > ESP)
    {
        m = (l + r) / 2;
        if (check(m))
        {
            l = m;
        }
        else
        {
            r = m;
        }
    }

    printf("%lf\n", l);

    return 0;
}