UVa 12462 - Rectangle

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在長條圖中,每一條有其的數值和顏色屬性,找到一個最大的面積,使得每一個顏色都出現過。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
6 3
2 3 1 7 3 5
2 0 1 0 1 2
3 1
2 2 2
0 0 0
5 2
3 2 1 2 3
1 0 1 0 1
6 4
1 2 3 4 5 6
0 1 2 3 1 0
7 2
1 2 3 4 3 2 1
0 1 0 1 0 1 0
10 2
2 1 2 1 1 2 1 2 2 1
1 0 0 0 1 0 0 1 1 0
3 2
1000000000 999999997 999999999
0 1 1
0 0

Sample Output

1
2
3
4
5
6
7
9
6
5
12
10
10
2999999991

Solution

對於每一個長條 h[i],勢必將往左往右延伸到第一個數值比較低的,因此會得到一個區間 [l, r],如果 [l, r] 之間不具有所有顏色,則忽略之。反之紀錄 h[i] * (r - l + 1) 是否為最大值。這樣的貪心方式,盡可能會具有最多的顏色,同時考慮到所有最大面積會卡住的地方。

但是窮舉找到每一個 [l, r] 相當費時,這裡運用單調堆的思路,分別從左、從右側往反方向掃描,掃描時維護堆裡面元素呈現遞減情況,分別找到左右端點後,檢查是否區間內有相符的顏色個數。

找所有左右端點只需要 O(n) 時間,但是檢查區間內的顏色個數是否符合則必須 O(nm)

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
#include <stdio.h>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;
#define MAXN 131072
#define MAXC 32
int h[MAXN], c[MAXN], sumc[MAXN][MAXC];
int L[MAXN], R[MAXN];
int main() {
int N, C;
while (scanf("%d %d", &N, &C) == 2 && N) {
for (int i = 1; i <= N; i++)
scanf("%d", &h[i]);
for (int i = 1; i <= N; i++)
scanf("%d", &c[i]);
for (int i = 1; i <= N; i++) {
for (int j = 0; j < C; j++)
sumc[i][j] = sumc[i-1][j];
sumc[i][c[i]]++;
}
for (int i = 0; i < C; i++)
sumc[N+1][i] = sumc[N][i];

h[0] = h[N+1] = 0;
stack<int> stk;
stk.push(0);
for (int i = 1; i <= N; i++) {
while (h[i] <= h[stk.top()])
stk.pop();
L[i] = stk.top() + 1, stk.push(i);
}

while (!stk.empty()) stk.pop();

stk.push(N + 1);
for (int i = N; i >= 1; i--) {
while (h[i] <= h[stk.top()])
stk.pop();
R[i] = stk.top() - 1, stk.push(i);
}

long long ret = 0;
for (int i = 1; i <= N; i++) {
int ok = 1;
for (int j = 0; j < C; j++)
ok &= sumc[R[i]][j] - sumc[L[i] - 1][j] > 0;
if (ok)
ret = max(ret, (long long) h[i] * (R[i] - L[i] + 1));
}
printf("%lld\n", ret);
}
return 0;
}
/*
6 3
2 3 1 7 3 5
2 0 1 0 1 2
3 1
2 2 2
0 0 0
5 2
3 2 1 2 3
1 0 1 0 1
6 4
1 2 3 4 5 6
0 1 2 3 1 0
7 2
1 2 3 4 3 2 1
0 1 0 1 0 1 0
10 2
2 1 2 1 1 2 1 2 2 1
1 0 0 0 1 0 0 1 1 0
3 2
1000000000 999999997 999999999
0 1 1
*/