---
title: "倒垃圾"
created: 2025-11-28
tags:
  - 算法
---

# 倒垃圾

## 题目 [倒垃圾](https://www.acwing.com/problem/content/description/4483/)

![[image-f376cf05.png]]

## 思路分析

二分思路：（参考上一题 [[学生和导师|学生和导师]]）

![[image-2ef52fff.png]]

双指针思路：

![[image-9cb540fd.png]]

一定能找到一个最大的小于a[i]的垃圾桶

二分找到的是O右边最近的△ 双指针找到的是O左边最近的△

## 代码实现

**二分实现**

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
const int N=2e5+10,INF=2e9;
int c[N],a[N],b[N];//用ab将c分开成 住宅a[]和垃圾桶b[]
int ans[N];
int n,m;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n+m;i++)  cin>>c[i];

    for(int i=0,cnt1=0,cnt2=0;i<n+m;i++){
        int t;  cin>>t;
        if(t)
            b[++cnt1]=c[i];
        else
            a[++cnt2]=c[i];
    }

    b[0]=-INF,b[m+1]=INF;//防止出现所有都小于或者所有都大于的极端情况 添加哨兵位
    for(int i=1;i<=n;i++){
        int r=lower_bound(b,b+m+2,a[i])-b;
        if((LL)a[i]-b[r-1]<=(LL)b[r]-a[i])
            ans[r-1]++;
        else
            ans[r]++;
    }
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<" ";
    return 0;
}
```

**双指针实现**

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
const int N=2e5+10,INF=2e9;
int c[N],a[N],b[N];//用ab将c分开成 住宅a[]和垃圾桶b[]
int ans[N];
int n,m;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n+m;i++)  cin>>c[i];

    for(int i=0,cnt1=0,cnt2=0;i<n+m;i++){
        int t;  cin>>t;
        if(t)
            b[++cnt1]=c[i];
        else
            a[++cnt2]=c[i];
    }

    for(int i=1,j=1;i<=n;i++){
        while(j+1<m && b[j+1]<=a[i])
            j++;
        //如果只有一个垃圾桶 就不存在左右比较选哪个的问题
        if(m==1){
            ans[j]++;
        }
        else{
            if((LL)a[i]-b[j]<=(LL)b[j+1]-a[i])
                ans[j]++;
            else
                ans[j+1]++;
        }
    }
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<" ";
    return 0;
}
```

## 同类题型

## 视频讲解

- [[2-Learning/02-算法/03-刷题理模型/双指针相关模型/匹配/倒垃圾|倒垃圾]]

---
⬅️ [[二分相关模型|二分相关模型]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/二分相关模型/借教室|借教室]]