[数据结构与算法]P2115 [USACO14MAR]Sabotage G(二分)

P2115 [USACO14MAR]Sabotage G(二分)

经典分数规划二分题。

这里注意解释下原理。

假设当前二分的答案是x，实际的答案是ans。

显然若x满足条件，则 x<=ans。我们的目的是找到ans。

所以l=mid。

时间复杂度：$O(nlogm)$

// Problem: P2115 [USACO14MAR]Sabotage G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2115
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2022-03-30 16:43:47
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
template <typename T>		//x=max(x,y)  x=min(x,y)
void cmx(T &x,T y){
	if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
	if(x>y) x=y;
}
int n;
int a[N];
const double eps = 1e-6;
double b[N];
double c[N],d[N];
bool ck(double x){
	rep(i,1,n) b[i] = a[i]-i*x;
	c[0] = 1e9;
	rep(i,1,n) c[i] = min(c[i-1],b[i]);
	double ans = -1e9;
	rep(i,1,n-2){
		ans = max(ans,b[i+1]-c[i]);
	}
	return b[n]-ans>=0;
	/*
	b_n - b_j + b_{i-1} >=0
	*/
}
int main(){
	/*
	sum -  sum_{i->j} / (n-(j-i+1))>=ans
	s_n - s_j + s_{i-1} >= (n-j+(i-1)) * ans
	s_n-n*ans - (s_j - j*ans) + (s_{i-1} - (i-1)*ans)
	*/
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]),a[i]+=a[i-1];
	double l = 0,r = 1e4;
	while(r-l>eps){
		double m = (l+r)/2;
		if(ck(m)) l = m;
		else r = m;
	}
	printf("%.3f\n",l);
	return 0;
}