【UVA1619】感觉不错 Feel Good([uva1619] feel good)

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;
}
————————

UVA1619 感觉不错 Feel Good

link

UVA1619 感觉不错 Feel Good (luogu.com.cn)

General idea of the topic

Given a sequence of positive integers \ (n \) and a long \ (n \), it is required to find a sub interval so that the sum of the numbers in this sub interval multiplied by the minimum value in the sub interval is the largest. Output this maximum and the two endpoints of the interval.

thinking

The left and right endpoints of the interval with each number as the minimum are processed by monotone stack.

For interval and, the prefix and \ (\ mathrm {sum}#i} \) can be recorded.

Then the final answer is \ (\ Max \ limits {I = 1} ^ {n} (\ mathrm {sum} {R {I-1} – \ mathrm {sum} {l_i}) \ cdot a_ i\)。

It’s not over yet. UVA has no SPJ, so we need to find the one with the smallest interval length when the answer is the largest. Moreover, the multi group data output format of UVA is also very outrageous. It is necessary to wrap lines in front of the second data.

code

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;
}