题目大意
有一天，小A得到了一个长度为n的序列。
他把这个序列的所有连续子序列都列了出来，并对每一个子序列都求了其平均值，然后他把这些平均值写在纸上，并对它们进行排序，最后他报出了第k小的平均值。
你要做的就是模仿他的过程。
题目分析
对于这一类不定长的平均值问题很难直接求出，因此考虑二分答案，问题转化为判定平均值$\lt x$的数量。
根据分数规划的思想考虑将每个数减去$x$，问题转化为统计和小于$0$的区间数量，做一个前缀和转化为逆序对问题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
LL n,k;
double a[maxn],b[maxn],c[maxn];
struct BIT {
int c[maxn];
#define lowbit(x) x&(-x)
void add(int x) {
for(int i=x; i<=n; i+=lowbit(i))c[i]++;
}
void clear(int x) {
for(int i=x; i<=n; i+=lowbit(i))c[i]=0;
}
int sum(int x) {
int ans=0;
for(int i=x; i>=1; i-=lowbit(i))ans+=c[i];
return ans;
}
} bit;
bool Check(double mid) {
b[1]=c[1]=0;
for(int i=1; i<=n; i++)c[i+1]=b[i+1]=b[i]+a[i]-mid;
sort(b+1,b+n+2);
int cnt=unique(b+1,b+n+2)-b-1;
LL ans=0;
for(int i=1; i<=n+1; i++)c[i]=lower_bound(b+1,b+cnt+1,c[i])-b;
for(int i=n+1; i>=1; i--) {
ans+=bit.sum(c[i]-1);
bit.add(c[i]);
}
for(int i=1; i<=n+1; i++)bit.clear(c[i]);
return ans<k;
}
int main() {
n=Get_Int();
k=Get_Int();
double Left=0,Right=0;
for(int i=1; i<=n; i++)a[i]=Get_Int(),Right=max(Right,a[i]);
while(Right-Left>1e-6) {
double mid=(Left+Right)/2;
if(Check(mid))Left=mid;
else Right=mid;
}
printf("%0.4lf\n",Left);
return 0;
}
|
