题解 P2070 【刷墙】

· · 题解

关于这道题，第一眼看到应该想到的是暴力吧，暴力很简单，读入后一个个打标记，最后统计一下从哪里到哪里经过的次数大于2次，再输出就好了。

但是，当我们再细细看题的时候： Bessie在她的行走中最远到达距起始点1,000,000,000个单位长度。

我的天！！！这个天才Bessie走这么远，我们要是乖乖开数组的话空间会不够的！！！这时我们又可以从什么方向入手呢？

我们回到我们一开始进行模拟的步骤，如果我们进行以下的移动的话会很简单： 3 R 2 L 3 R

0 1 2 3 4
1 2 2 2 1

（第一行是位置，第二行是经过次数）

但如果变成这样会很麻烦： 1000000 R 500000 L 1000000 R

。。。这个要是要写表格的话会死人的吧；但是这简单来写的话是不是这样呢？ 0 1 2 3 4 5 6 7 8 9
1 1 3 3 3 3 1 1 0 0
要是再简单点呢? 0 1 2 3
1 3 3 1

这时，一个熟悉的操作浮现在我们脑海中！！！

离散化！！！

如果我们用离散化，不正好符合刚刚我们偷懒的过程吗？这里1就代表了500000,2代表了1000000，3代表了1500000！！！妈妈再也不用担心我的空间不够了！！！

这时，我们就高高兴兴地写代码去啦，但是，写着写着，发现有什么不太对，我们这样做标记，岂不是要一个一个点的去判断？我的天，这太麻烦了，我们写代码的，不是要代码越简单越好吗？（其实就懒） 我们又想了想这个步骤，欸等等，这不正是我们学习差分的时候，老师说过的区间遍历这种类型吗！！！哈哈，没错就决定是你了！差分！

所以这道题我们用了两种技巧，一个是离散化，一个是差分，都是很实用的技巧呢！

最关键的一步来了！上代码！

#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

int n,a[2000010],b[2000010],c[2000010],now=0,ans=0,ok=0;
char A;

void deal(int last,int next){
    int v1 = lower_bound(b,b+1+n,last) - b;
    int v2 = lower_bound(b,b+1+n,next) - b;
    c[min(v1,v2)]++;c[max(v1,v2)]--;//差分的步骤 
}

int main(){
    cin>>n;
    a[0]=b[0]=c[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>A;
        if(A == 'L') a[i]*= -1;
        b[i]=b[i-1]+a[i];
    }
    sort(b,b+1+n);
    int m=unique(b,b+1+n) - b;//b数组就是用来离散化的   unique是去重函数 
    for(int i=1;i<=n;i++){
        deal(now,now+a[i]);
        now+=a[i];
    }
    ok=c[0];
    for(int i=1;i<m;i++){
        if(ok > 1) ans+=b[i]-b[i-1];
        ok+=c[i]; //差分后前缀和，标准步骤了吧 
    }
    cout<<ans<<endl;
    return 0;
}

本蒟蒻没写过几次代码，希望大家喜欢 orzorzorz