---
title: "救生员"
created: 2025-11-28
tags:
  - 算法
---

# 救生员

## 题目 [救生员](https://www.acwing.com/problem/content/1752/)

![[image-0332ac77.png]]

## 思路分析

首先想到用差分

雇用一头牛等于在一段里面++ 解雇一头牛等于--

存入所有的l,r 再枚举减去某一种的情况

分别构造前缀和 最后看非0的个数即可

这道题还有一个数据范围更大的版本

于是想到了用离散化 因为只需要用到的牛 不需要把整个数据范围构造前缀和

但是还是会tle

其实时间花在了每次移除一头牛 就要重新构造一次前缀和 这显然浪费时间 而且还有n次二分查找找映射位置

错的不冤（不过这也意味着现在能知道差分和离散化的用法场景了 也还不错）

然后也不难发现可以用区间合并

难点就在于 我怎么每次只挑几个做合并

因为这种操作不可逆 你想先合并了再删掉某段 答案会有问题

所以只能每次少挑一个做合并

这怎么办?

很巧妙的地方就是

两重for循环

当j=i的时候 我就不添加呗 这样其他的就都做了合并

每轮只有一个没做合并 等同于被删掉

(虽然这种在数据范围变大后也会tle emmm)

## 代码实现

**差分**

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

typedef pair<int,int> PII;

vector<PII> cows;

int b[N],s[N];

int n;

int main()

{

    cin>>n;

    for(int i=0;i<n;i++){

        int l,r;

        cin>>l>>r;

        cows.push_back({l,r});

        b[l+1]++;

        b[r+1]--;

    }

    int res=0;

    for(auto cow:cows){

        int num=0;

        int l=cow.first,r=cow.second;

        b[l+1]--;

        b[r+1]++;

        for(int i=1;i<N;i++){

             s[i]=s[i-1]+b[i];

             if(s[i]>0)

                num++;

        }

        res=max(res,num);

        b[l+1]++;

        b[r+1]--;

    }

    cout<<res<<endl;

    return 0;

}
```

数据范围变大后的离散化+差分

<https://www.acwing.com/problem/content/description/1748/>

虽然tle了 但是思路自卖自夸一下

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

typedef pair<int,int> PII;

vector<PII> cows;

vector<int> alls;

int b[N],s[N];

int n;

int find(int x){

    int l=0,r=alls.size()-1;

    while(l<r){

        int mid=l+r>>1;

        if(alls[mid]>=x)

            r=mid;

        else

            l=mid+1;

    }

    return r+1;

}

int main()

{

    cin>>n;

    for(int i=0;i<n;i++){

        int l,r;

        cin>>l>>r;

        cows.push_back({l,r});

        alls.push_back(l);

        alls.push_back(r);

    }

    sort(alls.begin(),alls.end());

    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(auto cow:cows){

        int l=find(cow.first),r=find(cow.second);

        b[l]++;

        b[r]--;

    }

    int res=0;

    for(auto cow:cows){

        int num=0;

        int l=find(cow.first),r=find(cow.second);

        b[l]--;

        b[r]++;

        for(int i=1;i<alls.size();i++){

             s[i]=s[i-1]+b[i];

             if(s[i]>0)

                num+=alls[i]-alls[i-1];

        }

        res=max(res,num);

        //还原现场

        b[l]++;

        b[r]--;

    }

    cout<<res<<endl;

    return 0;

}
```

**区间合并**

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

typedef pair<int,int> PII;

vector<PII> cows;

int n;

int main()

{

    cin>>n;

    for(int i=0;i<n;i++){

        int l,r;

        cin>>l>>r;

        cows.push_back({l,r});

    }

    sort(cows.begin(),cows.end());

    int res=0;

    for(int i=0;i<n;i++)

    {

        int sum=0,st=-1,ed=-1;

        for(int j=0;j<n;j++)

        {

            if(i!=j)

            {

                if(ed<cows[j].first)

                {

                    if(ed!=-1)

                        sum+=ed-st;

                    st=cows[j].first,ed=cows[j].second;

                }

                else if(ed<cows[j].second)

                    ed=cows[j].second;

            }

        }

        if(ed!=-1)

            sum+=ed-st;

        res=max(sum,res);

    }

    cout<<res<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/区间合并相关问题/改变数组元素|改变数组元素]] 🏠 [[00-刷题理模型]] ➡️ [[校门外的树|校门外的树]]