首页 > 代码库 > 51nod1711 平均数
51nod1711 平均数
Description
LYK有一个长度为n的序列a。
他最近在研究平均数。
他甚至想知道所有区间的平均数，但是区间数目实在太多了。
为了方便起见，你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。
Input
第一行两个数n,k(1<=n<=100000,1<=k<=n*(n+1)/2)。接下来一行n个数表示LYK的区间(1<=ai<=100000)。
Output
一行表示第k大的平均数，误差不超过1e-4就算正确。
Input示例
5 31 2 3 4 5
Output示例
4.000
思路
首先看题目求区间第k大，首先想到分第k大的平均数x。问题转化为如何快速求任意区间的平均数大于x的个数，先求求前缀和，则可以表示为(sum[r] - sum[l-1])/(r - l +1) > x 的区间个数，转化一下即为sum[r] - r*x > sum[l-1] - (l-1) * x;即形成一个新的数组sum[i]- i * x，求满足条件的区间有多少个，离散化一下，用树状数组统计一下就行。
注意：i从0开始，sum[0] = 0;也要算进去，不然会把0-1的区间漏掉。
Code
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define MAXN 100010 5 typedef long long ll; 6 using namespace std; 7 ll sum[MAXN]; 8 double a[MAXN],b[MAXN]; 9 int tree[MAXN];10 int n;11 ll k;12 13 int lowbit( int x)14 {15 return x & -x;16 }17 void add(int k)18 {19 while(k <= n + 1)20 {21 tree[k] ++;22 k += lowbit(k);23 }24 }25 int Sum(int k)26 {27 int sum = 0;28 while(k)29 {30 sum += tree[k];31 k -= lowbit(k);32 }33 return sum;34 }35 long long check(double x)36 {37 memset(tree, 0, sizeof(tree));38 for(int i = 0; i <= n; i++)39 a[i] = b[i] = sum[i] - i * x;40 sort(a, a + 1 + n);41 int num = unique(a, a + 1 + n) - a;42 long long ans = 0;43 for(int i = 0; i <= n; i++)44 {45 int temp = lower_bound(a, a + num, b[i]) - a + 1;46 ans += Sum(temp);47 add(temp);48 }49 return ans;50 }51 int main()52 {53 scanf("%d%I64d",&n,&k);54 int temp;55 sum[0] = 0;56 for(int i = 1; i <= n; i++)57 {58 scanf("%d",&temp);59 sum[i] = sum[i - 1] + temp;60 }61 double l = 1.0, r = 100000.0;62 while(r - l >= 1e-6)63 {64 double mid = (l + r) / 2.0;65 if (check(mid) >= k)66 l = mid;67 else68 r = mid;69 }70 printf("%.4f\n",(r + l)/2.0);71 return 0;72 }
51nod1711 平均数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。