USACO2005 City Skylineoj23401

题目大意：

Input

* Line 1: Two space separated integers: N and W

* Lines 2..N+1: Two space separated integers, the x and y coordinate of a point where the skyline changes. The xcoordinates are presented in strictly increasing order, and the first x coordinate will always be 1.

Output

* Line 1: The minimum number of buildings to create the described skyline.

Sample Input

10 261 12 25 16 38 111 015 217 320 222 1

Sample Output

6

Hint

INPUT DETAILS:

The case mentioned above

需要找到规律

题解：模拟一个单调栈，使栈内的元素递增。当新进来一个元素x时，while栈顶的元素大于当前x,ans++，将栈顶元素弹出如果栈顶元素等于x则只保留一个，ans不变最后加进去一个0元素把栈按照上述方式清空即可

#include <bits/stdc++.h> using namespace std; int main() { int n,w; while(~scanf("%d%d",&n,&w)) { stack <int> s; while(!s.empty()) s.pop(); int a,b,ans=0; for(int i=0;i<=n;i++) { if(i==n) b=0; else scanf("%d%d",&a,&b); if(!s.empty()) { while(!s.empty()&&b<s.top()) { ans++; s.pop(); } if(!s.empty()&&b==s.top()) s.pop(); s.push(b); } else s.push(b); } printf("%d\n",ans); } return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8403950.html

相关资源：JAVA上百实例源码以及开源项目