三分

三分

题目：

Weakness and Poorness

题意：

给一串整数 a1,a2,...,an $a_1,a_2,...,a_n$，求在所有 a1−x,a2−x,...,an−x $a_1-x,a_2-x,...,a_n-x$串中的最小Weakness值，Weakness定义为是对该串所有子串，求子串中数字的和的绝对值，其中的最大值

思路：

• 所有子串的和中，求最大值，这个是经典问题，O(n)可以解决，扫一遍序列，将当前值加入累计值，如果累计值为负就对累计值置零；
• 这里题目问的是子串的和的绝对值的最大值，这个也不难，对每个数取相反数，再做一次上述步骤，取两次结果的较大值即可
• 问题的难点在于，如何找到x，稍微计算一下样例，可以发现，串的Weakness值是先随着x的增大而减小，到达某个临界值后随着x的增大而增大，一个谷函数，三分枚举，O(n)验证，完成

代码：

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int maxn = 2e5 + 5;int arr[maxn];
double arr1[maxn];
int n;double calc(double arr[]){double t = 0;double res = arr[0];for (int i=0;i<n;++i){t = arr[i] + t;res = max(res, t);if (t < 0+eps){t = 0;}}return res;
}double solve(double t){for (int i=0;i<n;++i)arr1[i] = arr[i] - t;double x1 = calc(arr1);for (int i=0;i<n;++i)arr1[i] = -arr1[i];double x2 = calc(arr1);double x = max(fabs(x1), fabs(x2));return x;
}
int main(){scanf("%d",&n);int maximum = -10001, minimum = 10001;for (int i=0;i<n;++i){scanf("%d",arr+i);maximum = max(arr[i], maximum);minimum = min(arr[i], minimum);}int dcnt = 100;double l = minimum, r = maximum;while (dcnt--){double m1 = l + (r-l)/3, m2 = l + (r-l)*2/3;double x1 = solve(m1), x2 = solve(m2);if (x1 > x2){l = m1;}else r = m2;}double res=solve(l);printf("%.8f\n",res);return 0;}