刷墙

题目

Bessie从栅栏上的位置0开始,并且遵循着一个N次移动的次序(1 <= N <=
100,000)。例如“10 L”表示Bessie向左移动了10个单位长度,“15 R”表
示Bessie向右移动了15个单位长度。现给出Bessie所有移动的列表,Farmer
John想要知道哪些区域的栅栏至少涂了两层涂料(只涂一层涂料的区域可能在大雨
中被洗掉)。Bessie在她的行走中最远到达距起始点1,000,000,000个单位长度

输入输出格式

输入格式

第1行:一个整型数N。

第2..N+1行:每行描述了Bessie的N次移动中的一次,例如“15 L”。

输出格式:

1行:被至少涂了两层涂料的区域总数。

输入输出样例

输入样例

6

2 R

6 L

1 R

8 L

1 R

2 R

输出样例

6

思路

差分约束

将打标机的点用结构体记录下来

然后排序 一次累加 当累加器≥2时 更新ans

代码如下

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
54
55
56
57
58
59
60
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define LL long long
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; isdigit(ch); ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
struct node{int x, y;}a[100005<<1];int n;
bool comp(node x, node y){return x.x < y.x;}
inline int work()
{
in(n);
int last = 0;
F(i, 1, n)
{
int x; char ch; cin >> x >> ch;
if (ch == 'R')
{
a[i*2-1].y = 1;
a[i*2-1].x = last;
a[i*2].y = -1;
a[i*2].x = last+x;
last += x;
}
else
{
a[i*2-1].y = 1;
a[i*2-1].x = last-x;
a[i*2].y = -1;
a[i*2].x = last;
last -= x;
}
}
sort(a + 1, a + (n*2) + 1, comp);
int w = 0, ans = 0;
F(i, 1, n<<1)
{
if (w >= 2)
{
ans += a[i].x - a[i-1].x;
}
w += a[i].y;
}
printf("%d\n", ans);
return 0;
}
int TAT = work();
int main() {;}