粉刷栅栏

题目 粉刷栅栏

思路分析

和上一题基本一样

问题其实就是 粉刷过的话

就在这个区间++

所以还是用差分

想办法把向左向右移动转变成l，r+1的形式

不过注意的是 我们的区间与上一题不同 这次是左闭右开

从0走到2 2可是没被刷的 所以2就是那个r+1

所以在离散化时直接加入这个找到的r就够了 不必加1

最后要注意的一点就是

因为我们处理的是离散化后的差分数组

真实的被粉刷的栅栏数是不能用++算出的

得使用res+=alls[i] - alls[i - 1]

用记录的下标相减 这才是真实的长度

代码实现

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=2e5;
LL l[N],r[N],b[N];
vector<int> alls;
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;
    // return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}

int main()
{
    cin>>n;
    int idx=0,dis;
    char dir;
    for(int i=0;i<n;i++){
        cin>>dis>>dir;
        //注意 区间为左闭右开 从0走到2处 2并没有被刷 所以r不需要放+1
        if (dir == 'R'){
            l[i]=idx;
            r[i]=idx+dis;
            idx+=dis;
            alls.push_back(l[i]);
            alls.push_back(r[i]);
        }
        else if(dir=='L'){
            l[i]=idx-dis;
            r[i]=idx;
            idx-=dis;
            alls.push_back(l[i]);
            alls.push_back(r[i]);
        }
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(int i=0;i<n;i++){
        int L=find(l[i]),R=find(r[i]);
        b[L]++;
        b[R]--;
    }

    int res = 0, covered = 0;
    for (int i = 0; i < alls.size(); i++) {
        if (i) {
            covered += b[i - 1];
        }
        if (covered > 1) {
            res += alls[i] - alls[i - 1];// 累加被多次覆盖的区间长度
        }
    }

    cout<<res<<endl;

    return 0;
}

同类题型

视频讲解

• 粉刷栅栏

⬅️ 离散化相关问题 🏠 00-刷题理模型 ➡️ 赶牛入圈