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 閱讀(512) 評論(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;

}

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: POJ 3450 Corporate Identity---KMP or strstr or Suffix Array POJ 3613 Cow Relays---Floyd+矩陣相乘 POJ 1625 Censored!---AC 自動機+DP+高精度 POJ 3250 Bad Hair Day---棧的應用 POJ 3759 Simple Distributed computing system---最大流 POJ 1851 Map---計算幾何 POJ 1380 Equipment Box && POJ 2172 Bricks---計算幾何 POJ 2284 That Nice Euler Circuit---計算幾何 POJ 1931 Biometrics---計算幾何 POJ 3129 How I Wonder What You Are!----計算幾何

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Uriel's Corner

導航

留言簿(9)

文章分類(1191)

文章檔案(594)

搜索

積分與排名

最新評論

POJ 3250 Bad Hair Day---棧的應用