首页 > 代码库 > [CF612D] The Union of k-Segments（排序，扫描线）

[CF612D] The Union of k-Segments（排序，扫描线）

2024-09-19 00:33:00   216人阅读

题目链接：http://codeforces.com/contest/612/problem/D

题意：给n条线段，问覆盖了k次的区间有几个。

扫描线的思想，首先想到的是从左到右扫一遍，遇到出现被覆盖k次的端点，则开始计数，直到覆盖次数小于k为止。

其实可以用线段树做这道题，但是还有更巧妙的办法：

将左端点看作“入”，右端点看作“出”。每一个线段都是一个区间从入到出，入指的是覆盖次数+1，出指的是覆盖次数-1。

按照左端点升序排列，每遇到一个“入”则计数，并且判断当前计数值是不是等于k了，如果等于k，那说明当前“入”的点恰好是一个覆盖k次的区间的起点。

每遇到一个“出”，则判断一下当前点是不是cnt值为k，如果为k，那说明它恰好是一个覆盖k次区间的终点。插入后计数值-1即可。

这样扫描保证每次都是覆盖k次的区间成对出现。

我们排序希望先“入”后“出”，所以根据pair排序的规则，标记位"入"小于"出"即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 typedef pair<LL, LL> pll;
 6 const int maxn = 1000100;
 7 int n, k;
 8 vector<pll> cover;
 9 vector<LL> ret;
10 
11 int main() {
12     // freopen("in", "r", stdin);
13     LL x, y;
14     while(~scanf("%d%d",&n,&k)) {
15         cover.clear(); ret.clear();
16         for(int i = 1; i <= n; i++) {
17             scanf("%I64d%I64d",&x,&y);
18             cover.push_back(pll(x, 0));
19             cover.push_back(pll(y, 1));
20         }
21         sort(cover.begin(), cover.end());
22         int cnt = 0;
23         for(int i = 0; i < cover.size(); i++) {
24             if(cover[i].second == 0) {
25                 cnt++;
26                 if(cnt == k) ret.push_back(cover[i].first);
27             }
28             else {
29                 if(cnt == k) ret.push_back(cover[i].first);
30                 cnt--;
31             }
32         }
33         printf("%d\n", ret.size()/2);
34         for(int i = 0; i < ret.size()/2; i++) {
35             printf("%I64d %I64d\n", ret[i<<1], ret[i<<1|1]);
36         }
37     }
38     return 0;
39 }

 

[CF612D] The Union of k-Segments（排序，扫描线）


联系
我们