爱吃咸鱼的喵の无名小站 > UVa1619 感觉很好

UVa1619 感觉很好

2019-01-18

UVa1619 感觉很好 解题报告

题目链接
  这题使用单调栈，可以在$O(n)$时间内解决，单调栈还是不熟练，总结一下希望能提高吧。

题目分析

  题目的意思很简单，实际就是给定一个数组 A，在其中找出一个子序列$A[i]…A[j]$，使其满足$sum(A[i]+A[i+1]+…+A[j])*min(A[i],A[i-1],…,A[j])$为最大值。根据题目的要求，至少要设计出$O(n\log n)$的算法，当时我有以下几种思路：

  • 枚举起点，然后快速找到终点，不过这题好像没法在$O(1)、O(\log n)$时间内快速找到终点
  • 枚举子序列的长度，然后用滑动窗口判断，不过好像没法二分枚举，肯定会超时
  • 枚举最小值的可能位置，然后在$O(1)、O(\log n)$时间内算出，以当前枚举位置为最小值，满足条件的子序列最大值

  用贪心的思想，当最小值一定时，上述式子的长度越长，那么最后算出的值越大，所以我们只要找出，以当前枚举位置为最小值，向左向右最多能延伸多长即可。可以通过预处理出Left[i]、right[i]，表示i位置为最小值时，向左向右最多能延伸的位置。

算法设计

  现在的唯一问题就是，如何在$O(n)$时间内得到当前数字向左向右最大的延伸位置？
  不难想到，可以用单调栈+滑动窗口来实现，这样在统计的过程中，每个元素至多入队出队一次，时间复杂度为$O(n)$。具体思想就是，假设新加入的元素为 $a$ 那么，将栈中所有 大于等于 $a$ 的元素都出栈。出栈完毕后，栈顶元素位置即为当前元素能延伸到的最大位置，最后将当前元素入栈。
  说明如下：因为当栈中的一个元素大于 $a$ 时，它所能延伸到的位置，那么 $a$ 也一定能延伸到，而如果在栈中碰到一个小于 $a$ 的元素时，那么这个栈中元素的位置就是$a$ 能延伸到的最大位置。出栈条件是 $\geq$ 是因为需要尽量多的延伸，当相等时也要尽量往外延伸。

  总结一下单调栈的使用：

  • 首先确定入栈的元素是什么（是数组中的元素，还是数组的下标）
  • 确定单调栈中出栈的条件（大于还是小于，是否有等于）
  • 新加入的元素一定要在最后入栈
  • 注意栈为空的处理

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 100000 + 1000;
int A[maxn];
int n;
long long sum[maxn];
int stack[maxn];
int top;
int L[maxn], R[maxn];

int kcase = 0;

void solve()
{
	memset(sum, 0, sizeof(sum));
	//计算前缀和
	for (int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] +(long long) A[i];

	//利用单调栈预处理出 left[i]  表示第i个数字最左能延伸到的位置
	top = 0;
	memset(stack, 0, sizeof(stack));
	memset(L, 0, sizeof(L));
	memset(R, 0, sizeof(R));

	for (int i = 1; i <= n; i++)
	{
		//栈非空，而且栈顶元素大于当前元素，说明栈顶元素能延伸到的位置，当前元素一定能延伸到
		while (top > 0 && A[stack[top - 1]] >= A[i]) top--;
		
		L[i] = top == 0 ? 1 : (stack[top - 1] + 1);

		//当前元素入栈
		stack[top++] = i;
	}

	top = 0;
	memset(stack, 0, sizeof(stack));
	for (int i = n; i >= 1; i--)
	{
		while (top > 0 && A[stack[top - 1]] >= A[i]) top--;

		R[i] = top == 0 ? n : (stack[top - 1] - 1);

		stack[top++] = i;
	}

	int left=1, right=1;
	long long  max_val = 0;

	for (int i = 1; i <= n; i++)
	{
		long long  temp_val = (sum[R[i]] - sum[L[i] - 1])*(long long )A[i];

		if (temp_val > max_val ||( temp_val == max_val && (right - left) > (R[i] - L[i])))
		{
			max_val = temp_val;
			left = L[i];
			right = R[i];
		}
	}

	printf("%lld\n%d %d\n", max_val, left, right);
}

int main()
{
	freopen("C:\\Users\\lenovo\\Desktop\\test\\in.txt", "r", stdin);
	freopen("C:\\Users\\lenovo\\Desktop\\test\\out.txt", "w", stdout);
	while (scanf("%d", &n) == 1 && n)
	{
		if (kcase++) printf("\n");
		for (int i = 1; i <= n; i++)
			scanf("%d", &A[i]);
		solve();
	}
	return 0;
}