AcWing 1987. 粉刷栅栏

题目

1987. 粉刷栅栏 - AcWing题库

思路：

这道题一看就是差分，但是难就难在边界的判断上，即统计长度的时候应该考虑哪些端点，题目在这里没有表达清楚，统计区间时，区间应该是左闭右开，所以我们在差分的时候,就不用包括右端点

看了一下大家的题解大部分都是左闭右闭的，虽然在统计的时候方便求结果，但是不方便理解题面，在调试的过程中也很不清晰，而左闭右开在调试是可以清晰看到每一步，且与题面更相符

详解样例

输入样例：

6
2 R
6 L
1 R
8 L
1 R
2 R

输出样例：

6

样例解释

共有 6 单位长度的区域至少被涂抹 22 层油漆。

这些区域为 (−11,−8),(−4,−3),(0,2)。

如果按照左闭右闭那么样例的长度显然是9，而左闭右开显然是正确的

样例过程(排序后)：

跳的端点 :-11 跳过端点的次数:2
跳的端点 :-10 跳过端点的次数:2
跳的端点 :-8 跳过端点的次数:1
跳的端点 :-4 跳过端点的次数:3
跳的端点 :-3 跳过端点的次数:1
跳的端点 :0 跳过端点的次数:2
跳的端点 :2 跳过端点的次数:0

先上代码

题解：

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 100010;
map<int,int >b;//差分数组
vector<int>a;//a存跳过的每一个端点
int n;
int main()
{
    cin >> n;
    int x,idx = 0;
    a.push_back(0);
    char c;
    for (int i = 0; i < n; i ++ ){
        cin >> x>>c;
        
        if(c=='L'){
            b[idx-x]++;
          	//如果是左闭右开这里就是b[idx+1]--
            b[idx]--;
            idx-=x;
            a.push_back(idx);
        }else{
            b[idx]++;
          	//如果是左闭右开这里就是b[idx+x+1]--
            b[idx+x]--;
            idx+=x;
            a.push_back(idx);
        }
        
    }
  	//对a进行排序和判重
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());

    LL sum = 0,res = 0;
    int p = 0;
  	//如果想看清过程可以打开下面两句的注释
    for(auto i:a){
         //cout <<"跳的端点 :"<< i<<' ';
        if(sum<=1&&sum+b[i]>1)p = i;
        else if(sum>1&&sum+b[i]<=1)res+=i-p;
        sum+=b[i];
        //cout <<"跳过该端点的次数:" <&lt;sum &lt;&lt;endl;
    }
    cout &lt;&lt; res;
}

为什么要排序判重(其实map帮你实现了这两个过程)

排序是为了求差分

判重：我们是按照数从小到大去统计区间个数的，为了防止，多次跳过同一个点，这个点会既是左端点，也是右端点，以这个点为边界的区间就不会被统计到

这里其实也可以不用a数组(用a数组只是为了存点，不用更快)

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 100010;
#define x first
#define y second

map<int,int >b;

int n;
int main()
{
    cin >> n;
    int len,idx = 0;
    char c;
    for (int i = 0; i < n; i ++ ){
        cin >>len>>c;
        if(c=='L'){
            b[idx-len]++;
            b[idx]--;
            idx-=len;
        }else{
            b[idx]++;
            b[idx+len]--;
            idx+=len;
        }
        
    }
    LL sum = 0,res = 0; 
    int p = 0;
    for(auto i:b){
        if(sum<=1&&sum+i.y>1)p = i.x;
        else if(sum>1&&sum+i.y<=1)res+=i.x-p;
        sum+=i.y;
    }
    cout << res;
}