算法题(164):贴海报

审题：

本题需要我们找到贴完海报后可以直接看到的所有海报的个数

思路：
方法一：暴力模拟

我们可以直接模拟贴海报的过程，创建一个墙数组，每次贴海报就把对应位置的数组值改为海报编号，最后统计出的整个数组中海报的编号个数就是能看到的海报张数，直接输出即可

时间复杂度：我们需要进行m次贴海报，海报的数据范围是1e7，m的数据范围是1e3，乘起来会超时

方法二：离散化+模拟

由于本题的海报数据范围较大，但是海报张数的数据范围却较小，满足离散化使用前提。

所以我们使用离散化的算法将原海报区间映射到更小的区间上进行模拟

第一步：离散化海报区间

第二步：模拟贴海报过程

第三步：统计海报编号数

注意：如果我们在录入数据到离散化数组的时候没有给海报区间手动插入数据，可能会导致后面离散化区间后的海报编号情况与实际不同。

图示：

我们看到图示情况下，直接将数据录入disc数组可能会出现离散后统计结果与实际不同的情况，这是因为离散化后让区间缩短，如果不手动插入区间会导致离散区间异常重合

解题：
 

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 1010;
int n, m;
int a[N], b[N];
int disc[4 * N];
unordered_map<int, int> mp;//原始数据值，离散值
int pos;//离散后数据个数（无去重版本）
int f[4 * N];//模拟数组
bool judge[4 * N];//记录某海报是否已经被记录
int main()
{//数据录入cin >> n >> m;for (int i = 1; i <= m; i++){cin >> a[i] >> b[i];disc[++pos] = a[i]; disc[++pos] = a[i] + 1;disc[++pos] = b[i]; disc[++pos] = b[i] + 1;}//离散化处理sort(disc + 1, disc + 1 + pos);int cnt = 0;//去重后的离散数据个数for (int i = 1; i <= pos; i++){int x = disc[i];if (mp.count(x)) continue;cnt++;mp[x] = cnt;}//离散化后模拟贴海报for (int i = 1; i <= m; i++){int l = mp[a[i]];int r = mp[b[i]];for (int j = l; j <= r; j++){f[j] = i;}}//统计结果int answer = 0;for (int i = 1; i <= cnt; i++){int num = f[i];if (!num || judge[num]) continue;answer++;judge[num] = true;}cout << answer << endl;return 0;
}

1.由于我们手动插入了区间之间的空格，导致数据多了一倍，所以disc等数组就需要开4倍的N

2.统计结果的时候遇到为0编号的海报表示没有海报张贴，continue。

遇到已经看见过的海报也是continue，所以我们设置了judge数组

P3740 [HAOI2014] 贴海报 - 洛谷