题目
P2115 [USACO14MAR]破坏Sabotage
分析
AC代码
#include <iostream>
#include <cstdio>
using namespace std
;
int n
, sum
[100005];
double sufMax
[100005], preMin
[100005], c
[100005];
bool check(double mid
)
{
for (int i
= 0; i
<= n
; i
++)
{
c
[i
] = sum
[i
] - mid
* i
;
}
preMin
[1] = c
[1];
for (int i
= 2; i
<= n
; i
++)
{
preMin
[i
] = min(preMin
[i
- 1], c
[i
]);
}
sufMax
[n
- 1] = c
[n
- 1];
for (int i
= n
- 2; i
>= 1; i
--)
{
sufMax
[i
] = max(sufMax
[i
+ 1], c
[i
]);
}
for (int i
= 2; i
<= n
- 1; i
++)
{
if (sufMax
[i
] - preMin
[i
- 1] > c
[n
])
{
return 0;
}
}
return 1;
}
int main()
{
scanf("%d", &n
);
for (int i
= 1; i
<= n
; i
++)
{
int x
;
scanf("%d", &x
);
sum
[i
] = sum
[i
- 1] + x
;
}
double l
= 0, r
= 10005, mid
;
while (r
- l
> 1e-5)
{
mid
= (l
+ r
) / 2;
if (check(mid
))
{
l
= mid
;
}
else
{
r
= mid
;
}
}
printf("%.3lf", l
);
return 0;
}
