首页 > 代码库 > 离散化问题
离散化问题
描述
一天A和B所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，有些海报就会被其他社团的海报所遮挡住。看到这个场景，A便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢？于是B肩负起了解决这个问题的责任：因为宣传栏和海报的高度都是一样的，所以宣传栏可以被视作长度为L的一段区间，且有N张海报按照顺序依次贴 在了宣传栏上，其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示，其中a_i, b_i均为属于[0, L]的整数，而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了：究竟有几张海报能被看到呢？
输入
每个测试点（输入文件）有且仅有一组测试数据。每组测试数据的第1行为两个整数N和L，分别表示总共贴上的海报数量和宣传栏的宽度。每组测试数据的第2-N+1行，按照贴上去的先后顺序，每行描述一张海报，其中第i+1行为两个整数a_i, b_i，表示第i张海报所贴的区间为[a_i, b_i]。对于100%的数据，满足N<=10^5，L<=10^9，0<=a_i<b_i<=L。
输出
对于每组测试数据，输出一个整数Ans，表示总共有多少张海报能被看到。
样例输入
5 10
4 10
0 2
1 6
5 9
3 4
样例输出
5
1 #include <map> 2 #include <cmath> 3 #include <vector> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 #include <iostream> 8 #include <algorithm> 9 using namespace std;10 const int maxn = 100000 + 10;11 int N, L, M, a[maxn], b[maxn], f[maxn * 2];12 map<int, int> hash;13 14 int find(int x)15 {16 return f[x] == x ? x : f[x] = find(f[x]);17 }18 19 int main()20 {21 scanf("%d%d", &N, &L);22 hash[0] = 1;23 hash[L] = 1;24 for (int i = 0; i < N; i ++) {25 scanf("%d%d", &a[i], &b[i]);26 hash[a[i]] = 1;27 hash[b[i]] = 1;28 }29 for (map<int, int>::iterator iter = hash.begin(); iter != hash.end(); it ++) {30 M ++;31 f[M] = M;32 iter->second = M;33 }34 int Ans = 0;35 for (int i = N - 1; i >= 0; i --) {36 int x = hash[a[i]];37 int y = hash[b[i]] - 1;38 y = find(y);39 if (y >= x) {40 Ans ++;41 while (y >= x) {42 f[y] = y - 1;43 y = find(y);44 }45 }46 }47 printf("%d\n", Ans);48 return 0;49 }
离散化问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。