Massive Algorithms: NKOJ 2150 广告印刷

NKOJ 2150 广告印刷 - Monotone Queue

最近，afy决定给TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的N个建筑。
afy决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，
从左到右给出每个建筑物的高度H1,H2…HN，且0<Hi<=1,000,000,000，并且我们假设每个建筑物的宽度均为1。

要求输出广告牌的最大面积。

【输入文件】
输入文件 ad.in 中的第一行是一个数n (n<= 400,000)
第二行是n个数，分别表示每个建筑物高度H1,H2…HN，且0<Hi<=1,000,000,000。
【输出文件】
输出文件 ad.out 中一共有一行，表示广告牌的最大面积。
【输入样例】
6
5 8 4 4 8 4
【输出样例】

思路：

容易想到，要想使面积最大，肯定要将当前广告覆盖的楼房中，高度最小的那个楼房全部印刷上广告。所以，枚举每个建筑物的高度作为广告矩形的高度，求出在该楼房的左侧，有多少栋连续的楼房的高度大于或等于该楼房的高度，右侧同理。然后得到矩形广告的面积，找出最大面积即可

在这里约定，以当前建筑物为矩形高度，向两侧寻找可以印刷的建筑的过程叫做——扩展。

我们来考察从第i个建筑向左扩展的情况，h数组为建筑物高度，下标为1~n：

如果我们知道，向左扩展到极限时的建筑物的下标为j的话，这时，建筑物j是第一个满足h[j]<h[i]的建筑。那么，第i个建筑物向左扩展的建筑物数量为i-j-1。

如果，对h从左向右建立一个单调递增队列mq，h数组的下标为队列元素，在新的建筑物i要入队时，将队尾所有高度大于等于h[i]的元素都出队，新的队尾mq[rear-1]（rear指向队尾的下一个位置）刚好是上面所讲的向左扩展的极限下标j，因为入队顺序是从左向右的，而且在极限下标j与当前建筑下标i之间的这些建筑，因为高度大于等于h[i]，所有都出队了，mq[rear-1]就刚好是极限下标j。

向右侧扩展是同样的道理，只需要对h从右向左建立一个单调递增队列即可。

为了简化操作，将h[0]和h[n+1]的值都赋为-1。

下面举一个向左侧扩展的例子：

H[]存储建筑物高度，L[]记录向左扩展建筑数量。

下标	0	1	2	3	4
H[]	-1	9	5	5	-1
L[]

单调递增队列，front和rear分别为队首和队尾指针，rear指向队尾的下一个位置，初始时让0号建筑入队

指针	Front	Rear
队列元素	0

1号建筑入队，队尾没有比1号建筑更高的建筑，直接入队，L[1]= 1 - mq[rear-1] - 1，结果如下：

下标	0	1	2	3	4
H[]	-1	9	5	5	-1
L[]		0

指针	Front		Rear
队列元素	0	1

2号建筑入队，队尾元素为1号建筑，高度为9，比2号建筑高，所以出队，新的队尾元素为0号，计算L[2] = 2 –mq[rear-1] – 1，然后2号建筑入队尾，结果如下

下标	0	1	2	3	4
H[]	-1	9	5	5	-1
L[]		0	1

指针	Front		Rear
队列元素	0	2

3号建筑入队，队尾元素为2号建筑，高度为5，与3号建筑一样高，所以出队，新的队尾元素为0号，计算L[3] = 3 –mq[rear-1] – 1，然后3号建筑入队尾，结果如下：

下标	0	1	2	3	4
H[]	-1	9	5	5	-1
L[]		0	1	2

指针	Front		Rear
队列元素	0	3

最终结果：

下标	0	1	2	3	4
H[]	-1	9	5	5	-1
L[]		0	1	2

 6 int Q[N],h[N],head=0,tail=1,maxar=-1,kzleft[N],kzright[N],n;
 7 void input()
 8 {
 9     scanf("%d",&n);
10     for(int i=1;i<=n;++i)
11       scanf("%d",&h[i]);
12 }
13 void calcleft()
14 {
15     memset(Q,0,sizeof(Q));
16     h[0]=h[n+1]=-1;
17     for(int i=1;i<=n;++i)
18     {
19         while(head<tail&&h[Q[tail-1]]>=h[i])   tail--;
20         kzleft[i]=i-(Q[tail-1]);
21         Q[tail++]=i;
22     }
23 }
24 void calcright()
25 {
26     memset(Q,0,sizeof(Q));
27     head=0;tail=1;
28     Q[0]=n+1;
29     for(int i=n;i>=1;--i)
30     {
31         while(head<tail&&h[Q[tail-1]]>=h[i]) tail--;
32         kzright[i]=Q[tail-1]-i;
33         Q[tail++]=i;
34     }
35 }
36 int find_max_area()
37 {
38     for(int i=1;i<=n;++i)
39     {
40         maxar=max((kzleft[i]+kzright[i]-1)*h[i],maxar);          
41     }
42     return maxar;
43 }
44 int main()
45 {
46     input();
47     calcleft();
48     calcright();
49     printf("%d\n",find_max_area());
50     return 0;
51 }

https://blog.csdn.net/yskyskyer123/article/details/51131605

对于每一个建筑物，要知道往左到哪一个建筑第一个高度比它低，知道往右走哪一个建筑物第一个高度比它低。

可以用dp，也可以用单调队列。

首先从左往右，构造单增队列，这样始终有一个最小值，每加入一个高度h，先把队尾处大于等于它的高度全部删掉。

因为后面的高度，如果高度比h大，那么找到h就停止了，如果高度<=h，那么高度也一定<=删掉的元素。所以被删的元素不需要保留。

如果队列空了，证明h是从1开始到ind[h]的高度最小值。

https://blog.csdn.net/code_pang/article/details/14120027

https://www.jianshu.com/p/a4f2eecb1f89

最终的广告牌一定等于某个建筑物的高度×其能达到的最大长度
现在，建筑物的高度已知，现在只需要知道每个高度能达到的最大长度是多少。由于n是400000，我们只能用O（n）或O（nlogn）的算法。可以使用rmq，在后边的论文中会讲到。
现在讲时间复杂度为o（n）的单调队列的方法。
继续上边的思路，对于每个建筑物，只需要找到其能够扩展到的最大宽度即可。也就是这个建筑物的左右两边的比它低或等于它的建筑物个数。
如何用单调队列呢？
我们从1~n依次进队，维护一个单调递增序列。每次加入元素后维护其单调性，当然这样做必然会使一些元素出队，出队的元素一定要比当前加入的元素大，也就是说当前元素就是出队的元素能在右侧达到的最远的建筑物！
注意，要让h[n+1]=0并且让该元素入队一次（会使当前队列中的所有元素出队），保证每个元素都有其“右极限”的值。
要求“左极限”同理，只需从n~0循环即可，注意0
这道题是对单调队列的变形使用。由于问题的结果具有单调性，很好的利用出队元素的特性.

枚举法，时间复杂度为O(n^2)：

 1 int MaxRectArea(void)  
 2 {  
 3     int maxArea = 0;  
 4     int i, j;  
 5     for (i = 0; i < n; i++)  
 6     {  
 7         int count = 1;  
 8         //统计在当前建筑物i的左边，与h[i]相同或更高的建筑物有多少  
 9         for (j = i-1; j >= 0 && h[j] >= h[i]; j--)  
10         {  
11             count++;  
12         }  
13         //右边同理  
14         for (j = i+1; j < n && h[j] >= h[i]; j++)  
15         {  
16             count++;  
17         }  
18         int area = count * h[i];  
19         if (area > maxArea)  
20         {  
21             maxArea = area;  
22         }  
23     }  
24     return maxArea;  
25 }

NKOJ 2150 广告印刷 - Monotone Queue

Labels

Popular Posts