[C++知识库]1987. 粉刷栅栏 题解

跳转链接

https://www.acwing.com/problem/content/description/1989/

题目描述

农夫约翰发明了一种绝妙的方法来粉刷牛棚旁边的长栅栏（把栅栏想象成一维的数轴）。
他只需要在他最喜欢的奶牛贝茜身上挂一个刷子，然后在一旁悠闲的喝凉水就行了。
贝茜沿着栅栏来回走动时，会将她走过的栅栏部分涂上油漆。
贝茜从栅栏上的位置 0 处开始，共进行 N 次移动。
移动可能形如 10 L，表示向左移动 10 单位距离，也可能形如 15 R，表示向右移动 15 单位距离。
给定贝茜的 N 次移动列表，约翰想知道至少被涂抹了 2 层油漆的区域的总长度。
整个行进过程中，贝茜距离出发地的距离不会超过 109。

输入格式

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

输出格式

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

数据范围

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

输入样例

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

输出样例

6

样例解释

共有 6 单位长度的区域至少被涂抹 2 层油漆。
这些区域为 (?11,?8),(?4,?3),(0,2)。

题解思路

由于数据太大了 直接暴力数组模拟栅栏显然是不可以的
这道题和线段覆盖这道题类似 线段覆盖 具体讲解
线段覆盖这道题 要的是 覆盖点的数量 本题要的是栅栏长度
差分的时候 直接 L++,R - - 而不是 R + 1- - 这里要注意一下
例如区间 [0,2] 区间长度是2 差分的时候 0 + + 2- - 表示的是0~1这一段 0~1这一段长度就是2
如果 0++ 3- - 的话长度就是3了 0~2
所以我们就把所有边界点离散 然后求一遍前缀和 每段区间的和 就是这段区间覆盖的次数
其实和数组模拟一样 只不过是把所有边界点离散了 然后 每段区间R - L 就是这个区间的长度 也就是被覆盖的长度
然后看一下每段区间被覆盖多少次就好 答案要的是至少覆盖两次以上

代码

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

map<int, int> b;
int n, x, y;
char s[2];

int main()
{
	scanf("%d", &n);
	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 sum = 0, res = 0, last;
	for(auto [k, v] : b)
	{
		if(sum >= 2) res += k - last;
		sum += v; //sum不会一直都>=2，会在某个右端点被减小
		last = k;
	}
	
	printf("%d", res);
	return 0;
}