粉刷栅栏（寒假每日一题 8）

粉刷栅栏（寒假每日一题 8）

农夫约翰发明了一种绝妙的方法来粉刷牛棚旁边的长栅栏（把栅栏想象成一维的数轴）。

他只需要在他最喜欢的奶牛贝茜身上挂一个刷子，然后在一旁悠闲的喝凉水就行了。

贝茜沿着栅栏来回走动时，会将她走过的栅栏部分涂上油漆。

贝茜从栅栏上的位置 0 0 0 处开始，共进行 N N N 次移动。

移动可能形如 10 L，表示向左移动 10 10 10 单位距离，也可能形如 15 R，表示向右移动 15 15 15 单位距离。

给定贝茜的 N N N 次移动列表，约翰想知道至少被涂抹了 2 2 2 层油漆的区域的总长度。

整个行进过程中，贝茜距离出发地的距离不会超过 1 0 9 10^9 109。

输入格式
第一行包含一个整数 N N N。

接下来 N 行，每一行包含一个行动指令，诸如 10 L 或 15 R。

输出格式
输出至少被涂抹了 2 2 2 层油漆的区域的总长度。

数据范围
1 ≤ N ≤ 1 0 5 1≤N≤10^5 1≤N≤105
整个行进过程中，贝茜距离出发地的距离不会超过 1 0 9 10^9 109。
每次指令移动距离的取值范围是 [ 1 , 2 × 1 0 9 ] [1,2×10^9] [1,2×109] 。

输入样例：

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

输出样例：

6

样例解释
共有 6 6 6 单位长度的区域至少被涂抹 2 2 2 层油漆。

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

解题思路

离散化 + 差分

解法一（map）

离散化此处用 m a p map map 代替！！！

#include<iostream>
#include<map>using namespace std;int main(){map<int, int> b;int n;scanf("%d", &n);int x = 0, y;char s[2];while(n--){scanf("%d%s", &y, s);if(*s == 'R'){// 差分b[x]++;b[x + y]--;x += y;  // 表示当前所处的位置}else{b[x - y]++;b[x]--;x -= y;}}int res = 0, sum = 0, last;  // sum是b[]的前缀和for(auto p: b){int x = p.first;int v = p.second;// 前缀和大于等于2的话if(sum >= 2) res += x - last;  // 加区域长度sum += v;  // 前缀和last = x;  // 更新左区间位置}printf("%dn", res);return 0;
}

解法二（离散化）

#include<iostream>
#include<map>
#include<algorithm>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 100010;int a[N];int main(){int n;scanf("%d", &n);int x = 0, y;char s[2];vector<PII> op;vector<int> q;q.push_back(0);while(n--){scanf("%d%s", &y, s);if(s[0] == 'R') op.push_back({x, x + y}), x += y;else op.push_back({x - y, x}), x -= y;q.push_back(x);}sort(q.begin(), q.end());q.erase(unique(q.begin(), q.end()), q.end());for(auto o: op){int l = o.x;int r = o.y;l = lower_bound(q.begin(), q.end(), l) - q.begin();r = lower_bound(q.begin(), q.end(), r) - q.begin();a[l]++;a[r]--;}int res = 0, sum = 0, last;  // sum是b[]的前缀和for(int i = 0; i < q.size(); i++){int x = q[i];int v = a[i];// 前缀和大于等于2的话if(sum >= 2) res += x - last;  // 加区域长度sum += v;  // 前缀和last = x;  // 更新左区间位置}printf("%dn", res);return 0;
}