求连续区间数组均值最大(区间内个数规定最小值)
一维数组(POJ 2018)
题意:给定一个非负序列,求长度大于F的连续子序列的平均数最大
解法:在实数上二分平均数mid,判断a中是否有长度大于F平均数大于等于mid,再进行调整二分区间
设定一个b数组,b[i]=a[i]-mid
当b[i]的区间和大于等于0的时候说明区间平均数大于等于mid
用sum数组表示b数组前缀和
再求出长度大于等于F的所有区间中的最大区间和=前缀和-前面的最小前缀和(要保证区间长度大于F)
判读和是否大于等于0。
AC代码:
#include<iostream>
#include<cstdio>
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
#define ll long long
using namespace std;
const int maxn = 1e5;
int n,F;
double a[maxn+5],b[maxn+5],sum[maxn+5];
// b数组为a数组减去平均数mid,所以只要某一段和非负即说明平均数大于mid
// 求 b 长度大于F的子串和非负
bool ok(double mid){
fo(i,1,n) b[i]=a[i]-mid;
// b 前缀和
fo(i,1,n){
sum[i] = sum[i-1] + b[i];
}
double min_val = 1e10,ans=-1e10;
fo(i,F,n){
min_val = min(sum[i-F], min_val); // 前面(0~i-F)的最小前缀和
ans = max(ans, sum[i]-min_val);
}
return ans>=0;
}
void solve(){
double l=-1,r=2000,eps=1e-4; // 2分平均数 ,eps一定要比题目精确度大,本题1e-3,可以取1e-5
while(r-l>eps){
double mid = (l+r)/2;
if(ok(mid)) l=mid;
else r=mid;
}
cout<<int(r*1000)<<endl; // 二分实数,取上界(当精确度小于题目精确度的时候L可以的时候R也必定可以,取大故取R)
}
int main(){
while(scanf("%d%d",&n,&F)==2){
fo(i,1,n)scanf("%lf",&a[i]);
solve();
}
return 0;
}
二维数组拓展(牛客oj暑期训练)
https://ac.nowcoder.com/acm/contest/11255/J
题解:把题目转化为分别找第一项的最大值与第二项的最大值的和,由于题目给的大小为1e5我们可以用二分来找最大值。
AC代码:
#include<bits/stdc++.h>
#define ll double
using namespace std;
const int N = 1e5 + 20;
ll a[N], b[N], ans[N] = {0};
//POJ 2018
bool check(ll x, ll *v, int tx, int t) {
for (int i = 1; i <= t; i++) {
ans[i] = v[i] + ans[i - 1] - x;
}
ll mini = 0;
for (int i = tx; i <= t; i++) {
mini = min(mini, ans[i - tx]);
if (ans[i] - mini >= 0) return true;
}
return false;
}
ll f(ll *v, int tx, int t) {
ll l = 0, r = 1e6, eps = 1e-7;
while (r - l > eps) {
ll mid = (l + r) / 2;
if (check(mid, v, tx, t))l = mid;
else r = mid;
}
return l;
}
int main() {
ios::sync_with_stdio(false);
int n, m, x, y, i;
cin >> n >> m >> x >> y;
for (i = 1; i <= n; i++)cin >> a[i];
for (i = 1; i <= m; i++)cin >> b[i];
printf("%.10lf\n", f(a, x, n) + f(b, y, m));
return 0;
}