实数二分+前缀和维护
调了一晚上, 但发现没什么注意事项orz
无输出只因eps定义成了int型QAQ哭唧唧
#include#include using namespace std;const int sz = 100010;double eps = 1e-5;int n, f;double a[sz], b[sz], sum[sz];bool check(double k) { double minn = 1e10, ans = -1e10; for(int i = 1; i <= n; i++) b[i] = a[i] - k; for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + b[i]; for(int i = f; i <= n; i++) { minn = min(minn, sum[i - f]); ans = max(ans, sum[i] - minn); } if(ans >= 0) return true; else return false;}int main() { scanf("%d%d", &n, &f); for(int i = 1; i <= n; i++) scanf("%lf", &a[i]); double l = -1e6, r = 1e6, ans = 0; while(r - l > eps) { double mid = (l + r) / 2.0; if(check(mid)) l = mid; else r = mid; } cout<< int(r * 1000) <