首页 > 代码库 > PKU 2528 Mayor's posters

PKU 2528 Mayor's posters

2024-07-17 10:39:22   218人阅读

题意：

　　一个公告板上面贴海报，宽度都是一样的，长度可能不一样。后面的海报可能把前面的覆盖掉。问最后能看见多少张不同的海报。

思路：

　　这题原来做过，是用线段树的区间染色写的。记录每个区间是纯色还是杂色。最后统计所有颜色。

　　今天发现可以用一种类似扫描线的想法来做。想象一条扫描线从左往右走。用set来维护当前位置对应的海报集合。然后记录当前位置最新(能被看到)的海报是哪一张。

　　最后统计一下能被看见的海报数量。

 

代码:

　　

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <time.h>15 16 using namespace std;17 18 const int INF = 1<<30;19 const int MAXN = (int) 1e4+55;20 21 struct event {22     int x, t; //位置，时间23     int status; //进还是出24 25     void init(int xx, int tt, int ss) {26         x = xx;27         t = tt;28         status = ss;29     }30 31     bool operator < (const event &_) const {32         if (x!=_.x) return x<_.x;33         //同一位置时，入边在出边前面34         //同是入边时，时间大的在前面35         //同是出边时，时间小的在前面36         return status*t > _.status*_.t;37     }38 }a[MAXN<<1];39 40 set<int> S;41 bool vis[MAXN];42 int n;43 44 void solve() {45     S.clear();46     memset(vis, false, sizeof(vis));47     int l, r;48 49     scanf("%d", &n);50     for (int i = 0; i < n; i++) {51         scanf("%d%d", &l, &r);52         a[i<<1].init(l, i+1, 1);53         a[i<<1|1].init(r+1, i+1, -1);54     }55     sort(a, a+n*2);56 57     int ans = 0;58     set<int>::iterator p;59 60     for (int i = 0; i < n*2; i++) {61         if (a[i].status>0) S.insert(a[i].t);62         else S.erase(a[i].t);63         if (!S.empty()) {64             p = S.end(); p--;65             if (!vis[*p]) {66                 ans++;67                 vis[*p] = true;68             }69         }70     }71     printf("%d\n", ans);72 }73 74 int main() {75     #ifdef Phantom0176         freopen("PKU2528.txt", "r", stdin);77     #endif //Phantom0178 79     int T;80     scanf("%d", &T);81     while (T--) {82         solve();83     }84 85     return 0;86 }
View Code

 


联系
我们