倒垃圾

题目 倒垃圾

image-f376cf05

思路分析

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

image-2ef52fff

双指针思路：

image-9cb540fd

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

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

代码实现

二分实现

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

双指针实现

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

同类题型

视频讲解

⬅️ 二分相关模型 🏠 00-刷题理模型 ➡️ 借教室