贪心

TODO：畜栏预定、雷达设备

区间问题

贪心题的要点：

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

acwing905

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

#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;
}

python

from functools import cmp_to_key

class point:
    def __init__(self,a,b):
        self.a =  a
        self.b =  b

def cmp(x, y):
    if x.b != y.b:
        return x.b - y.b  # 按右端点升序排序
    return x.a - y.a      # 右端点相同则按左端点升序

n = int(input())

points = []

for i in range(n):
    a,b = map(int,input().split())
    points.append(point(a,b))

points.sort(key=cmp_to_key(cmp))

cnt = 0
right = -1e9-10
for i in range(n):
    if points[i].a > right:
        cnt += 1
        right = points[i].b
        
print(cnt)

acwing908

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

cpp

#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;
    
}

python

from functools import cmp_to_key


class point:
    def __init__(self,a,b):
        self.a =  a
        self.b =  b


def cmp(x, y):
    if x.b != y.b:
        return x.b - y.b  # 按右端点升序
    return y.a - x.a      # 右端点相同则按左端点降序
    
points = []
    
n = int(input())

for i in range(n): 
    a,b = map(int,input().split())
    points.append(point(a,b))
    
    
points.sort(key=cmp_to_key(cmp))

righ = -1e9-10
cnt = 0
for i in range(n):
    if points[i].a > righ:
        cnt += 1
        righ = points[i].b

print(cnt)

区间选点问题和最大不相交区间数量

1. 按右端点排序保证贪心最优性
2. 跨过当前右端点的区间都会被后续的点覆盖
3. 计数逻辑在数学上完全等价

acwing906

python

acwing907