学校的宣传板 计蒜客

题目

分析

做题思路：这道题我们要倒过来想，从后面的海报开始贴，一旦这个位置贴了海报，就不贴了，然后统计贴上去的海报的个数就可以了。

**留意点：**这个宣传板最长可达10^9米，但是n张海报的位置信息最多2 * 10^4,(最多10 ^4 张海报，一张海报2个位置信息)，这里如果我们根据宣传板的长度去开标记数组的长度，铁定内存超限，所以就用到离散化，只用开 2*10^4长度的标记数组就可以了。

AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;

const int MAXN=1e4+1;//最多MAXN张海报
int num[MAXN*2];//一张海报2个位置信息，最多MAXN*2个位置信息
bool vis[MAXN*2];//标志这个地图的每个列是否有海报
int n,m;
map<int,int> mp;
struct poster{
    int l,r;
}p[MAXN];

int main()
{
    memset(vis,false,sizeof(vis));//全部位置初始化为没有贴海报
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){//录入n张海报的位置信息
        scanf("%d%d",&p[i].l,&p[i].r);
        num[i*2]=p[i].l;
        num[i*2+1]=p[i].r;
    }
    sort(num,num+2*n);//标准的离散化过程，先排序，再去重，最后映射
    int len=unique(num,num+n*2)-num;
    for(int i=0;i<len;i++){
        mp[num[i]]=i+1;
    }
    int ans=0;//存储结果
    for(int i=n-1;i>=0;i--){//从后面的海报往前遍历，后面的海报贴上了，则该处的位置就不能贴海报了
        int l=mp[p[i].l];
        int r=mp[p[i].r];
        int flag=0;//用于标志此张海报的是否有贴上去。
        for(int j=l;j<=r;j++){
            if(!vis[j]){
                vis[j]=true;
            }
            else flag++;
        }
        if(flag!=r-l+1)ans++;//只要没贴上的长度不等于海报长度，则这张海报可以看到。
    }
    printf("%d\n",ans);
    return 0;//give me five
}