畜栏预定

贪心

TODO：畜栏预定、雷达设备

贪心题的要点：

  • 思考、证明通过该方法得到的解是最优解，可用res <= ans，res >= ans ——> res == ans。

acwing905

我们通过重载运算符，设置为通过右端点从小到大排序，获取第一个右端点最大值为max值，若其他线段的左端点小于该max值，则continue。若大于则更新max值，res++。

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

#include <algorithm>
#include <iostream>

using namespace std;
const int N = 100010;

struct st {
  int lef;
  int rig;
  bool operator<(const st &tmp) const { return this->rig < tmp.rig; }
} st[N];

int main() {
  int n;
  cin >> n;     //别忘了输入n Qwq
  for (int i = 0; i < n; i++) {
    cin >> st[i].lef >> st[i].rig;
  }
  sort(st, st + n);
 
  int max = -2e9;
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (st[i].lef > max) {
      max = st[i].rig;
      res++;
    }
  }
  cout << res << endl;
}

acwing908

这题可以采用右端点排序，也可以采用左端点排序。

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
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 1e5 + 5;


struct st{
    int lef;
    int rig;
    bool operator< (const st& tmp)  const{
        return this->rig < tmp.rig;
    }
}st[N];


int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> st[i].lef >> st[i].rig; 
    }
    sort(st,st + n);
    int res = 0;
    int rigmax  = -2e9;
    for(int i = 0; i < n; i ++)
    {
        if(st[i].lef > rigmax)
        {
            rigmax = st[i].rig;
            res ++;
         }
    }
    cout << res << endl;
    
}