3
3
2016
0

[BZOJ1683] [Usaco2005 Nov]City skyline 城市地平线

水题

以后交题目一定要检查调试有没有删掉

因为这个WA了一次……

简单的单调栈

#include<cstdio>
#include<stack>
using namespace std;

stack<int> S;

int n,w,ans,f[500005]={0};

int main(){
freopen("1683.in","r",stdin);
freopen("1683.out","w",stdout);
scanf("%d %d",&n,&w);
for(int i=1;i<=n;i++){
	int tpa,tpb;
	scanf("%d %d",&tpa,&tpb);
	int last=-1;
	while(!S.empty() && S.top()>tpb){int res=S.top();S.pop();if(res!=last){ans++;last=res;}}
	S.push(tpb);
}
while(!S.empty()){
	if(f[S.top()]==0 && S.top()){
		f[S.top()]++;
		ans++;
	}
	S.pop();
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 303

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com