UVA1619 感觉不错 Feel Good
链接
UVA1619 感觉不错 Feel Good (luogu.com.cn)
题目大意
给出正整数 \(n\) 和一个长 \(n\) 的数列,要求找出一个子区间,使这个子区间的数字和乘上子区间中的最小值最大。输出这个最大值与区间的两个端点。
思路
用单调栈处理出每个数作为最小值的区间的左端点和右端点。
对于区间和,可以记录前缀和 \(\mathrm{sum}_{i}\)。
那么最后答案就是 \(\max\limits_{i=1}^{n}(\mathrm{sum}_{r_{i-1}}-\mathrm{sum}_{l_i})\cdot a_i\)。
到这里还没有结束,UVa 没有 SPJ,所以要找到答案最大的情况下区间长度最小的。而且 UVa 的多组数据输出格式也很离谱,要在第二个数据开始在前面换行。
代码
const int N = 1e5 + 10;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n;
ll a[N], l[N], r[N], s[N], q[N];
ll ans, ansl, ansr;
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
for (bool flag = 0; scanf ("%d", &n) != EOF; ) {
flag? putchar(10): flag = 1;
for (int i = 1; i <= n; i++)
a[i] = Read(),
s[i] = s[i - 1] + a[i];
ans = a[1], ansl = ansr = 1;
int t = 0; q[0] = 0;
for (int i = 1; i <= n; i++) {
for (; t && a[q[t]] >= a[i]; t--);
l[i] = q[t], q[++t] = i;
}
t = 0; q[0] = n + 1;
for (int i = n; i; i--) {
for (; t && a[q[t]] >= a[i]; t--);
r[i] = q[t], q[++t] = i;
}
for (int i = 1; i <= n; i++) {
ll tmp = a[i] * (s[r[i] - 1] - s[l[i]]);
if (ans < tmp || (ans == tmp && r[i] - l[i] - 1 < ansr - ansl + 1))
ans = tmp, ansl = l[i] + 1, ansr = r[i] - 1;
}
printf ("%lld\n%lld %lld\n", ans, ansl, ansr);
}
return 0;
}