lightoj1083

27 8月 2015

1083 - Histogram

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3 measured in units where the width of the rectangles is 1.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case contains a line with an integer N (1 ≤ N ≤ 30000) denoting the number of rectangles. The next line contains N space separated positive integers (≤ 30000) denoting the heights.

Output

For each case, print the case number and the largest rectangle that can be made.

Sample Input	Output for Sample Input
272 1 4 5 1 3 354 4 3 2 4	Case 1: 8Case 2: 10

Note

Dataset is huge; use faster I/O methods.

题目类型：单调队列

算法分析：一道经典的使用单调队列思想解的题。坐标从小到大分析，如果存在一个高度不超过先前的高度，则应该将先前高度的矩形块的面积出栈并计算，更新最大值。否则就一直入栈。最后将还在栈中的矩形块的面积计算出来并更新最大值

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 1100 + 66;

struct Node
{
    int w, h;
    Node (int ww, int hh) : w (ww), h (hh) {}
    Node () {}
};


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);

        int n;
        scanf ("%d", &n);

        deque <Node> deq;

        int hei, maxval = -INF, temp_w;

        for (int i = 0; i < n; i++)
        {
            scanf ("%d", &hei);

            temp_w = 0;
            Node val;
            while (!deq.empty () && deq.back ().h >= hei)
            {
                val = deq.back ();
                deq.pop_back ();
                maxval = max (maxval, val.h * (val.w + temp_w));
                temp_w += val.w;
            }

                deq.push_back (Node (temp_w + 1, hei));
        }

        temp_w = 0;
        while (!deq.empty ())
        {
            Node val = deq.back ();
            deq.pop_back ();
            maxval = max (maxval, val.h * (temp_w + val.w));
            temp_w += val.w;
        }

        printf ("%d\n", maxval);
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1100 + 66;

struct Node

{

int w, h;

Node (int ww, int hh) : w (ww), h (hh) {}

Node () {}

};

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int n;

scanf ("%d", &n);

deque <Node> deq;

int hei, maxval = -INF, temp_w;

for (int i = 0; i < n; i++)

{

scanf ("%d", &hei);

temp_w = 0;

Node val;

while (!deq.empty () && deq.back ().h >= hei)

{

val = deq.back ();

deq.pop_back ();

maxval = max (maxval, val.h * (val.w + temp_w));

temp_w += val.w;

}

deq.push_back (Node (temp_w + 1, hei));

}

temp_w = 0;

while (!deq.empty ())

{

Node val = deq.back ();

deq.pop_back ();

maxval = max (maxval, val.h * (temp_w + val.w));

temp_w += val.w;

}

printf ("%d\n", maxval);

}

return 0;

}

lightoj1080

lightoj1088

一	二	三	四	五	六	日
« 6月
		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

超客的水墨烟雨

lightoj1083

Input

Output

Sample Input

Output for Sample Input

Note

分类目录

标签云

书签

近期评论