解題區/解題區 - UVa

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
*/