题解 P3740 【[HAOI2014]贴海报】

· · 题解

震惊！25行代码解决。

我做这道题没有想太多，因为海报高度和墙一样高，所以可以直接看做是一个线段。

然后先声明一个数组a，输入一个区间就把这个区间的数组覆盖成这张海报的序号，最后只要数这个数组里有多少不一样的数就是可见的海报数。

看完大佬的题解之后觉得好像非常高深，原本以为是过不了的。一边直接AC ~~没想到竟然过了。 附上代码

#include<iostream>
using namespace std;
int a[10000001],b[10000001];
int main()
{
    int n,m,tot=0;
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        for(int j=x;j<=y;++j)
            a[j]=i;
    }
    for(int i=1;i<=n;++i)
    {
        if(b[a[i]]==0&&a[i]!=0)
        {
            b[a[i]]++;
            tot++;
        }
    }
    cout<<tot;
    return 0;
}