最小区间覆盖
题意: 给定m个区间(左右端点)，求最少用多少个区间能覆盖1 - n
思想 :
- 将所有线段按左端点升序排序
- 另s = 0，用t进行备份，在左端点不超过的s + 1的前提下找到最远的右端点
即while(l <= t + 1) s = max(s, r); - 更新完后判断if(s >= r)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std;
const int N = 1e5 + 5;
typedef pair<int, int> PII;
PII a[N];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i ++)
scanf("%d %d", &a[i].l, &a[i].r);
sort(a, a + m);
int s = 0, idx = 0, ans = 0, t;
while(s < n && idx < m)
{
if(a[idx].l > s + 1)
{
cout << "-1";
return 0;
}
t = s; //开始的位置需要备份， 直到左端点大于 t + 1时退出，这时t再进行更新
while(a[idx].l <= t + 1 && idx < m)
{
s = max(s, a[idx].r); //得到可选择中的右边点的最远点
idx ++;
}
ans ++;
t = s;
}
if(s == n) cout << ans; //是否达到目标
else cout << "-1";
return 0;
}
畜栏预定
有N头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。
给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B，每头牛在[A,B]这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
输入格式
第1行：输入一个整数N。
第2..N+1行：第i+1行输入第i头牛的开始吃草时间A以及结束吃草时间B，数之间用空格隔开。
输出格式
第1行：输入一个整数，代表所需最小畜栏数。
第2..N+1行：第i+1行输入第i头牛被安排到的畜栏编号，编号从1开始，只要方案合法即可。
数据范围
1≤N≤50000,
1≤A,B≤1000000
输入样例：
1 | 5 |
输出样例：
1 | 4 |
方法: 按照起点对所有区间进行排序，然后用小顶堆维护一个最小的右区间，
如果右区间 >= 新的左区间，说明只能建立一个新的畜栏 小顶堆更新即可
如果右区间 < 左区间，说明可以放在最小右区间那一行中，更新小顶堆即可
当前最优解为 k
证明:
反证法:
假设存在 m < k 为最优解，另处理第m + 1 牛时为 i，由于是按顺序枚举，则m.l <= i.l，枚举第i头牛时会出现 m.r >= i.l的情况则会出现包含的情况，
需要m + 1个围栏，以此类推到最优解k个1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
const int N = 50000 + 5;
typedef pair<int, int> PII;
pair<PII, int> cows[N]; //cows[i].second 记录当前的编号
int id[N]; //默认顺序，之后进行排序会打乱
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> cows[i].first.first >> cows[i].first.second;
cows[i].second = i;
}
sort(cows + 1, cows + n + 1); //按区间左端点排序
priority_queue<PII, vector<PII>, greater<PII>> q; //小顶堆维护最小右区间
for(int i = 1; i <= n; i ++)
{
if(q.empty() || q.top().first >= cows[i].first.first) //如果为空或最小右区间大于l，则必须加一个围栏
{
PII t = {cows[i].first.second, q.size() + 1}; //牛栏编号为i
id[cows[i].second] = t.second; //记录编号
q.push(t); //入堆
}
else
{
PII now = q.top(); //和最小右区间一个栅栏
q.pop();
now.first = cows[i].first.second; //右区间会被更新
id[cows[i].second] = now.second; //这个牛也在这个栅栏
q.push(now); //i继续入堆，让其维护最小的右区间
}
}
cout << q.size() << endl;
for(int i = 1; i <= n; i ++)
cout << id[i] << endl; //按输入顺序，顺序输出每头牛 的栅栏编号
return 0;
}
区间选点覆盖
雷达设备
假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。
每个小岛都位于海洋一侧的某个点上。
雷达装置均位于海岸线上，且雷达的监测范围为d，当小岛与某雷达的距离不超过d时，该小岛可以被雷达覆盖。
我们使用笛卡尔坐标系，定义海岸线为x轴，海的一侧在x轴上方，陆地一侧在x轴下方。
现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。
输入格式
第一行输入两个整数n和d，分别代表小岛数目和雷达检测范围。
接下来n行，每行输入两个整数，分别代表小岛的x，y轴坐标。
同一行数据之间用空格隔开。
输出格式
输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出“-1”。
数据范围
1≤n≤1000
输入样例：
1 | 3 2 |
输出样例：
1 | 2 |
思想方法，先将题目进行转化，由勾股定理转化为区间问题: 给定n个区间，
用最少的点数让每个去区间至少包含一个点
做法: 先让区间按照右端点进行排序，然后判断当前左区间是否大于 last(右区间) ，如果大于则 ans ++
证明: 假设上述选择出来的区间有 m 个，由于右区间按升序排序，且当前左区间大于上一个的右区间，
即每条线段都不相交，那么至少需要m个点来被包含1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using namespace std;
typedef pair<double, double> PDD;
const double eps = 1e-6; //浮点数比大小
const int N = 1008;
PDD p[N];
int main()
{
int n, x, y, d;
double len;
cin >> n >> d;
for(int i = 0; i < n; i ++)
{
scanf("%d %d", &x, &y);
if(d < y) { cout << "-1"; return 0; }
auto len = sqrt(d * d - y * y); //两次使用，一次定义
p[i] = {x + len, x - len}; //转化为线段(利用勾股定理)
}
sort(p, p + n); //按右端点升序排列
int ans = 0;
double last = -1e10; //上一个的右区间，由于第一个线段必定覆盖则定义为 -inf，让第一个必定满足
for(int i = 0; i < n; i ++)
if(p[i].second > last + eps) //小于等于不用更新，相减大于eps则满足条件
{
ans ++;
last = p[i].first; //更新为当前的右区间
}
cout << ans;
return 0;
}