题解【洛谷P2070】刷墙

题面

将每一次移动的距离进行差分，前缀和判断移动的距离是否\(\geq 2\)即可。

#include <bits/stdc++.h>
#define itn int
#define gI gi

using namespace std;

typedef long long ll;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

inline ll gl()
{
    ll f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

const int maxn = 100003;

int n, ans, now, sum;
struct Node
{
    int x, cf;
} a[maxn * 2];

inline bool cmp(Node x, Node y) {return x.x < y.x;}

int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    n = gi();
    for (int i = 1; i <= n; i+=1)
    {
        int x = gi(); 
        char s;
        scanf("%c", &s);
        if (s == 'L')
        {
            a[i * 2 - 1] = (Node){now, -1};
            a[i << 1] = (Node){now - x, 1};
            now -= x;
        }
        else 
        {
            a[i * 2 - 1] = (Node){now, 1};
            a[i << 1] = (Node){now + x, -1};
            now += x;
        }
    }
    sort(a + 1, a + 1 + (n << 1), cmp);
    //for (int i = 1; i <= (n << 1); i+=1) cout << a[i].x << ' ' << a[i].cf << endl;
    now = a[1].cf;
    for (int i = 2; i <= n * 2; i+=1)
    {
        if (now >= 2) ans += a[i].x - a[i - 1].x;
        now += a[i].cf;
    }
    printf("%d\n", ans);
    return 0;
}

题解【洛谷P2070】刷墙

原文：https://www.cnblogs.com/xsl19/p/12244868.html