粉刷栅栏

题目描述

题目链接：1987. 粉刷栅栏 - AcWing题库

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

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

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

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

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

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

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

代码

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n;
        Map<Integer,Integer> m = new TreeMap<>( (a,b) -> a-b );
        n = in.nextInt();
        int idx = 0;
        for(int i = 1; i <= n; i ++)
        {
            int x;
            String s;
            x = in.nextInt();
            s = in.next();
            if(s.equals("L"))
            {
                m.put(idx, m.getOrDefault(idx, 0) - 1);
                idx -= x;
                m.put(idx, m.getOrDefault(idx, 0) + 1);

            }
            else
            {
                m.put(idx, m.getOrDefault(idx, 0) + 1);
                idx += x;
                m.put(idx, m.getOrDefault(idx, 0) - 1);
            }
        }
        long sum = 0, ans = 0;
        int p = 0;
        for(int i : m.keySet())
        {
            if(sum <= 1 && sum + m.get(i) > 1)
                p = i;
            else if(sum > 1 && sum + m.get(i) <= 1)
                ans += i - p;
            sum += m.get(i);
        }
        System.out.println(ans);
        in.close();
    }

}

/*
6
2 R
6 L
1 R
8 L
1 R
2 R
*/