题目描述
数据范围
解法
二分答案。
对于一个答案mid，要求出区间平均数小于mid的个数ans。
给所有数减去mid，那么问题转化为求出所有区间和为负数的个数。
对于一个区间[l,r]，如果sum[r]-sum[l-1]<0，那么这个区间和就为负数。
算出前缀和后，利用归并排序对逆序对计数。
ans即为这个计数器的值。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
const char* fin="ave.in";
const char* fout="ave.out";
const int inf=0x7fffffff;
const int maxn=100007;
int n,m,i,j,k;
double l,r,mid;
ll ans;
int a[maxn];
double sum[maxn],xsum[maxn];
void mergesort(int l,int r){
int i,j,k,mid=(l+r)/2;
if (l==r) return ;
mergesort(l,mid);
mergesort(mid+1,r);
i=l;
j=mid+1;
k=l;
while (i<=mid && j<=r){
if (sum[i]>=sum[j]){
xsum[k++]=sum[j++];
ans+=mid-i+1;
}else xsum[k++]=sum[i++];
}
while (i<=mid) xsum[k++]=sum[i++];
while (j<=r) xsum[k++]=sum[j++];
for (i=l;i<=r;i++) sum[i]=xsum[i];
}
bool judge(double v){
sum[0]=0;
for (i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i]-v;
}
ans=0;
mergesort(0,n);
return ans>=m;
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
l=0;
r=10e9;
while (r-l>10e-6){
mid=(l+r)/2;
if (judge(mid)) r=mid;
else l=mid;
}
printf("%.4lf",l);
return 0;
}启发
又一次刷新了我对所有区间问题的认识。
让我觉得问题套路层出不穷，似乎找不着规律。
很久之前就接触过这题，但是当时并没有太重视。
虽然知道是二分答案，但是知道是要求区间和为负数时就无从下手。
明明是很简单的问题，但是就是转不出脑袋里的死胡同。
心里一心想着分治，因为之前的题目种种显示是所有区间问题可以利用分治、动态规划等来解决。
然后找不着头绪。
其实归并排序找逆序对也算是分治。
但是并没有想出是要找逆序对的个数。
导致遇到这道题不知所措。
还是要多练习问题的转化。
本道题主要思路：
第k大平均数->二分
区间平均数小于mid->区间和为负->前缀和的逆序对等同于区间负