Luobuyu's Blog

0%

1987.粉刷栅栏

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 1.5k 阅读时长 ≈ 1 分钟
类似区间加，但是需要使用离散化进行处理。

1987. 粉刷栅栏

题目描述：

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

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

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

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

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

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

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

输入格式

第一行包含一个整数 $ N $ 。

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

输出格式

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

数据范围

$ 1 \le N \le 10^5 $
整个行进过程中，贝茜距离出发地的距离不会超过 $ 10^9 $ 。
每次指令移动距离的取值范围是 $ [1,2 \times 10^9] $ 。

输入样例：

1
2
3
4
5
6
7
6
2 R
6 L
1 R
8 L
1 R
2 R

输出样例：

1
6

题解：

首先可以发现如果数据范围比较小的话，使用数组就可以存下，然后使用区间加就可以得到结果。

但是数据范围太大，开不下这么大的数组，而且时间复杂度太高。可以发现区间比较少，只有 $ 10^5 $ 个，因此可以考虑离散化。

离散化：即是映射，通常用来把长的区间映射为数组上的点，或者把比较大的数值映射为比较小的数值。区间映射到点，实际上也是比较大的数值映射比较小的数值。

该题使用的连续的长度，和区间加还不太一样。可以使用区间左端点代替整个区间，将连续的区间变成离散的点，这样就可以使用区间加了。

image-20220117141611387

可以使用 map 来做映射，最后遍历 map 计算当前值，统计长度。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
map<int, int> mp;
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int l = 0, length;
    char dir;
    // 以区间的左端点，代替整个区间
    for (int i = 1; i <= n; i++)
    {
        cin >> length >> dir;
        if (dir == 'L')
        {
            l -= length;
            mp[l]++;
            mp[l + length]--;
        }
        else
        {
            l += length;
            mp[l - length]++;
            mp[l]--;
        }
    }
    int cur = 0;
    int last = 0;
    int ans = 0;
    for (auto kv : mp)
    {
        if (cur > 1)
        {
            ans += kv.first - last;
        }
        cur += kv.second;
        last = kv.first;
    }
    cout << ans << endl;
    return 0;
}