题目描述
有一天,小 A 得到了一个长度为 的序列。
他把这个序列的所有连续子序列都列了出来,并对每一个子序列都求了其平均值,然后他把这些平 均值写在纸上,并对它们进行排序,最后他报出了第 小的平均值。
你要做的就是模仿他的过程。
思路
Algorithm ( pts)
考虑直接枚举每个子序列,然后计算平均数,使用前缀和优化做到 。
Algorithm ( pts)
考虑二分答案,问题转化为是否有 个区间的平均数大于 。
形式化地,设 ,然后询问 ,如果答案为 ,那就让 ,否则 。
设 ,然后就有:
然后我们可以做一个等式变形(以区间 为例):
然后设 ,然后就变为了
这个式子很熟悉吧,是不是就是逆序对。
然后我们就可以把 数组求出来,求逆序对即可。
但是有一个问题,你会漏掉统计 的区间,那就是需要再加上 的位置。然后就做完了。
时间复杂度: 。
代码
#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;
}