题目描述

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

思路

Algorithm 114040 pts)

考虑直接枚举每个子序列,然后计算平均数,使用前缀和优化做到 Θ(n2)\Theta(n^2)

Algorithm 22100100 pts)

考虑二分答案,问题转化为是否有 kk 个区间的平均数大于 xx

形式化地,设 f(l,r)=i=lraif(l,r) = \sum\limits_{i=l}^r a_i,然后询问 [i=1nj=in[f(i,j)x]k][\sum\limits_{i=1}^n\sum\limits_{j=i}^n[f(i,j) \le x] \le k],如果答案为 truetrue,那就让 lmidl \leftarrow mid,否则 rmidr \leftarrow mid

Si=k=1iaiS_i = \sum\limits_{k=1}^i a_i,然后就有:

f(i,j)=SiSj1f(i,j) = S_i - S_{j-1}

然后我们可以做一个等式变形(以区间 [i+1,j][i+1,j] 为例):

SjSijix\frac{S_{j} - S_{i}}{j-i} \le x

SjSix×jx×iS_j - S_i \le x \times j-x \times i

Sjx×jSix×iS_j - x \times j \le S_i - x \times i

然后设 bi=Six×ib_i = S_i - x \times i,然后就变为了

bjbi(ij)b_j \le b_i(i \le j)

这个式子很熟悉吧,是不是就是逆序对。

然后我们就可以把 bb 数组求出来,求逆序对即可。

但是有一个问题,你会漏掉统计 [1,k](k[1,n])[1,k](k \in [1,n]) 的区间,那就是需要再加上 Sii×x<0bi<0S_i - i\times x < 0 \Rightarrow b_i < 0 的位置。然后就做完了。

时间复杂度: Θ(nlognlogmax{a})\Theta(n \log n \log \max\{a\})

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;

vector<double> Ave;
double A[MAXN], b[MAXN], a[MAXN];
long long N, K;
double L, R, mid;
long long Ans;

void Merge(int l1 ,int r1 ,int l2 ,int r2) {
    int tot = 0;
    while(l1 <= r1 && l2 <= r2) {
        if(a[l1] <= a[l2]) {
            b[++tot] = a[l1++];
 
        }
        else {
            b[++tot] = a[l2++];
            Ans += r1 - l1 + 1;
        }
    }
    while(l1 <= r1) b[++tot] = a[l1++];
    while(l2 <= r2) b[++tot] = a[l2++];
    for(int i = tot, j = r2; i >= 1; i--, j--) {
        a[j] = b[i];
    }
}
void MergeSort(int l ,int r) {
    if(l < r) {
        int mid = (l + r) >> 1;
        MergeSort(l , mid);
        MergeSort(mid + 1 , r);
        Merge(l , mid , mid + 1 , r);
    }
}

long long Check(double x) {
	Ans = 0;
	for (int i = 1; i <= N; i++) {
		a[i] = A[i] - x + a[i - 1];
		if (a[i] < 0) Ans++; 
	}
	MergeSort(1, N);
	return Ans;
}

int main() {
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		R = max(R, A[i]);
	}
	while (R - L >= 1e-7) {
		mid = (L + R) / 2;
		if (Check(mid) < K) L = mid;
		else R = mid;
	}
	printf("%.4lf\n" ,L);
	return 0;
}