Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3250 Bad Hair Day---栈的应用

Posted on 2010-10-21 15:08 Uriel 阅读(496) 评论(0)  编辑 收藏 引用 所属分类: POJ 、数据结构
        跟别人Compare得到的水题，虽然是想拿来轻松一下，不过还是有些收获的~
        看完题本来想5min切掉的，结果搞了半小时。。= =。。思路有点混乱。。。
 
        stk[i]表示牛i右侧不比i低的第一头牛，累加更新。。(单步之后才搞清楚。。)

        加了读入优化之后32Ms。。还行。。

//Problem: 3250  User: Uriel 
//Memory: 1004K  Time: 32MS 
//Language: G++  Result: Accepted 

#include<stdio.h>
#include<stdlib.h>

int stk[80010],a[800010];

int in(){
    char ch;
    int a=0;
    while((ch=getchar())==' ' || ch=='\n');
    a*=10;
    a+=ch-'0';
    while((ch=getchar())!=' ' && ch!='\n'){
        a*=10;
        a+=ch-'0';
    }
    return a;
}

int main(){
    int i,j,n,k=1;
    __int64 res=0,t;
    n=in();
    for(i=0;i<n;++i)a[i]=in();
    a[n]=0x3fffffff;
    for(i=n-1;i>=0;--i){
        t=0;
        stk[i]=i+1;
        while(a[i]>a[stk[i]] && stk[i]<n){
            t+=stk[stk[i]]-stk[i];
            stk[i]=stk[stk[i]];
        }
        res+=t;
    }
    printf("%I64d\n",res);
    return 0;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理