USACO14MAR Sabotage 发表于 2018-08-04 | 分类于 USACO | 字数统计: 251 字 题目地址 题解二分答案,设为$ans$,那么判定条件 移项,等价于 求右边的最大值即可。123456789101112131415161718192021222324252627282930313233343536373839404142#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cctype>#define INF 1000000000using namespace std;typedef long long ll;int read(){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; }int n,a[100005];double eps=1e-4,sum[100005]={0}; bool C(double ans){ double mini=sum[1]-ans,maxi=sum[2]-2*ans-(sum[1]-ans); for(int i=2;i<n;i++){ maxi=max(maxi,sum[i]-(double)i*ans-mini); mini=min(mini,sum[i]-(double)i*ans); } return (sum[n]-(double)n*ans<=maxi);}void init(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i];}void solve(){ double L=0,R=(a[1]+a[n])*0.5,M; while(R-L>eps){ M=(R+L)*0.5; if(C(M))R=M;else L=M; } printf("%.3lf\n",L);}int main(){ init(); solve(); return 0;}
v1.5.2