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^5^ 整个行进过程中，贝茜距离出发地的距离不会超过 10^9^。 每次指令移动距离的取值范围是 [1,2×10^9^]。

输入样例 ​

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;
}