P3467(矩形覆盖问题)

#include <bits/stdc++.h>

using namespace std;

int n,a[],b[];

int q[],p[];

map<int,int>m;

int ans;

int main()

{

    cin>>n;

    int ans=;

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

        cin>>a[i]>>b[i];

    int tail=,head=;

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

    {

        while(tail>=head&&q[tail]>=b[i])

        {

            if(q[tail]==b[i])    ans++;

            tail--;

        }

        q[++tail]=b[i],p[tail]=i;

    }

    cout<<n-ans;

}

巴特西

P3467(矩形覆盖问题)

最新文章

热门文章

巴特西

P3467(矩形覆盖问题)

1.考虑如果整个建筑物链是等高的，一张高为链高，宽为整个建筑物宽的海报即可完全覆盖；

2.若有两个不等高的元素组成建筑物链，那么一定需要两张；

3.因为题目要求海报不可超出建筑物链，那么我们即可用单调栈维护：初始海报数为建筑物数，入栈建筑物链的高度序列，当栈顶大于即将入栈元素时弹栈，若最后弹栈元素与即将入栈元素等高，需要的海报数-1；

4.易证明本方法是正确的：当有两个处于一个峰两侧的等高块时，他们可以用一张海报覆盖，所需海报数显然可减少一个；

最新文章

热门文章