蓝桥杯线段和点贪心

问题描述

　　有n个点和m个区间，点和区间的端点全部是整数，对于点a和区间[b,c]，若a>=b且a<=c，称点a满足区间[b,c]。
　　求最小的点的子集，使得所有区间都被满足。

输入格式

　　第一行两个整数n m
　　以下n行每行一个整数，代表点的坐标
　　以下m行每行两个整数，代表区间的范围

输出格式

　　输出一行，最少的满足所有区间的点数，如无解输出-1。

样例输入

5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9

样例输出

数据规模和约定

　　1<=n,m<=10000
　　0<=点和区间的坐标<=50000

转载自https://blog.csdn.net/starlet_kiss/article/details/104982470

贪心是弱项，输出中间变量跟着样例跑了一遍，然后模模糊糊理解了一丢丢。

待复习。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxx = 10010;
 4 struct node{
 5     int s; //start，区间的左端点
 6     int e; //end，区间的右端点 
 7 } p[maxx]; //区间数组 
 8 bool cmp(node n1, node n2) { 
 9     if (n1.s != n2.s) {
10         return n1.s < n2.s;
11     }
12     return n1.e > n2.e;
13 }
14 int a[maxx]; //存储点 
15 int main() {
16     int n, m;
17     cin >> n >> m; 
18     for (int i = 1; i <= n; i++) { //n个点 
19         cin >> a[i];
20     }
21     for (int i = 1; i <= m; i++) { //m个区间 
22         cin >> p[i].s >> p[i].e;
23     }
24     sort(p + 1, p + 1 + m, cmp);
25     int k, i, j, st = 1;
26     for (k = 1; k <= n; k++) { //操作的次数=最少需要的点数 
27         //cout << "-------------------" << k << endl;
28         int _max = -1;
29         for (i = 1; i <= n; i++) { //遍历所有点 
30             //cout << "----------" << i << endl;
31             for (j = st; j <= m; j++) {
32                 if (p[j].s > a[i] || p[j].e < a[i]) {
33                     //cout << "--j:" << j << " break " << endl;
34                     break;
35                 }
36             } 
37             if (j > _max) { //看这个点最多可以满足多少个区间。
38                 _max = j;
39                 //cout << "-_max:" << _max << endl;
40             }
41         }
42         st = _max; //下次开始的时间就在上一次点的地方开始，寻找满足的点
43         //cout << "--st:" << st << endl;
44         if (st == m + 1) { //所有的线段满足了，就直接退出。
45             break;
46         }
47     }
48     if (k == n + 1) {
49         cout << -1 << endl;
50     } else {
51         cout << k << endl;
52     }
53     return 0;
54 }

蓝桥杯 线段和点 贪心

推荐阅读

蓝桥杯线段和点贪心