POJ - 2082 - Terrible Sets【单调队列】题解

红太狼 2021-07-25 02:01 373阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

Let N be the set of all natural numbers \{0 , 1 , 2 , . . . \}, and R be the set of all real numbers. wi, hi for i = 1 . . . n are some elements in N, and w0 = 0.  
Define set B = \{< x, y > | x, y ∈ R and there exists an index i > 0 such that 0 <= y <= hi ,∑0<=j<=i-1wj <= x <= ∑0<=j<=iwj\}  
Again, define set S = \{A| A = WH for some W , H ∈ R+ and there exists x0, y0 in N such that the set T = \{ < x , y > | x, y ∈ R and x0 <= x <= x0 +W and y0 <= y <= y0 + H\} is contained in set B\}.  
Your mission now. What is Max(S)?  
Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy.  
But for this one, believe me, it’s difficult.  
**Input**  
The input consists of several test cases. For each case, n is given in a single line, and then followed by n lines, each containing wi and hi separated by a single space. The last line of the input is an single integer -1, indicating the end of input. You may assume that 1 <= n <= 50000 and w1h1+w2h2+…+wnhn < 109.  
**Output**  
Simply output Max(S) in a single line for each case.  
**Sample Input**  
3  
1 2  
3 4  
1 2  
3  
3 4  
1 2  
3 4  
\-1  
**Sample Output**  
12  
14

### 2.代码 ###

#include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    ll h[maxn]; //高度 
    ll w[maxn]; //宽度 
    ll sum[maxn]; //前缀和 
    int l[maxn];  //左边界 
    int r[maxn];  //右边界 
    int s[maxn];  //模拟栈 
    int main()
    { 
    	int N;
    	int top;
    	while(cin>>N && N>0)
    	{ 
    	    sum[0]=0;
            for(int i=1;i<=N;i++)
    		{ 
    			scanf("%d",&w[i]);
    			scanf("%d",&h[i]);
    			sum[i]=sum[i-1]+w[i];
    			l[i]=i;
    			r[i]=i;
    		}
    		top=0;
    		for(int i=1;i<=N;i++)   //向左找
    		{ 
    			while(top&&h[i]<=h[s[top]])//从栈低到栈顶递增 
                    top--;
                if(top==0)
                    l[i]=1;
                else
                    l[i]=s[top]+1;//s[top]存的数的值肯定是比a[i]小的，所以地s[top]+1个位置即为所求
                s[++top]=i;
    		}
    		top=0;
    		for(int i=N;i>=1;i--)  ///向右找 
    		{ 
    			while(top && h[i]<=h[s[top]])
                    top--;
                if(top==0)
                    r[i]=N;
                else
                    r[i]=s[top]-1;
                s[++top]=i;
    		}
    		ll ans=0;
    		ll area;
    		for(int i=1;i<=N;i++)
    		{ 
    			area=h[i]*(sum[r[i]]-sum[l[i]-1]);
    			ans=max(ans,area);
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }