USACO2005 City Skyline /// oj23401

题目大意：

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 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

Sample Output

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=;

            for(int i=;i<=n;i++)

            {

                if(i==n) b=;

                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 ;

}

巴特西

USACO2005 City Skyline /// oj23401

最新文章

热门文章