BZOJ1113: [Poi2008]海报PLA【单调栈+二分】

【题目描述】

传送门

【题解】

对于相同高度的,我们可以合并,但是要求中间没有小于这个高度的,所以单调栈+二分就可以了。

代码如下

#pragma GCC optimize(2)
#include<cstdio>
#include<cctype>
using namespace std;
const int MAXN=250005;
int n,Top,Stk[MAXN],Ans;
bool Fnd(int x){
    for(register int L=1,R=Top,mid=(R+L)>>1;L<=R;mid=(R+L)>>1){
        if(Stk[mid]==x) return 1;
        if(Stk[mid]<x) L=mid+1;else R=mid-1;
    }
    return 0;
}
inline int read(){
    register int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1113.in","r",stdin);
    freopen("1113.out","w",stdout);
    #endif
    n=read();
    for(register int i=1,x;i<=n;i++){
        read(),x=read();
        if(!Fnd(x)) Ans++;
        while(Stk[Top]>=x&&Top) Top--;
        Stk[++Top]=x;
    }
    printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部