题目描述
Farmer John has devised a brilliant method to paint the long fence next to his barn (think of the fence as a one-dimensional number line). He simply attaches a paint brush to his favorite cow Bessie, and then retires to drink a cold glass of water as Bessie walks back and forth across the fence, applying paint to any segment of the fence that she walks past.
Bessie starts at position 0 on the fence and follows a sequence of N moves (1 <= N <= 100,000). Example moves might be "10 L", meaning Bessie moves 10 units to the left, or "15 R", meaning Bessie moves 15 units to the right. Given a list of all of Bessie's moves, FJ would like to know what area of the fence gets painted with at least K coats of paint. Bessie will move at most 1,000,000,000 units away from the origin during her walk.
Farmer John 想出了一个给牛棚旁的长围墙涂色的好方法。（为了简单起见，我们把围墙看做一维的数轴，每一个单位长度代表一块栅栏）他只是简单的把刷子蘸满颜料，系在他最喜欢的奶牛Bessie上，然后让Bessie来回地经过围墙，自己则在一旁喝一杯冰镇的凉水。（……-_-|||) Bessie 经过的所有围墙都会被涂上一层颜料。Bessie从围墙上的位置0出发，并将会进行N次移动(1 <= N <= 100,000)。比如说，“10 L”的意思就是Bessie向左移动了10个单位。再比如说“15 R”的意思就是Bessie向右移动了15个单位。给出一系列Bessie移动的清单。FJ 想知道有多少块栅栏涂上了至少K层涂料。注意：Bessie最多会移动到离原点1,000,000,000单位远的地方。
输入输出格式
输入格式：
-
第1行： 两个整数： N K
- 第2...N+1 行： 每一行都描述了Bessie的一次移动。 （比如说 “15 L"）
输出格式：
- 一个整数：被至少涂上K层涂料的栅栏数
（注意：输出的最后一定要输出换行符！否则会WA）
输入输出样例
6 2
2 R
6 L
1 R
8 L
1 R
2 R
6
说明
PS1：来源：usaco jan silver P01 想看原题的请戳http://www.usaco.org/index.php?page=viewproblem2&cpid=226）
PS2：测试数据也可以在在http://www.usaco.org/index.php?page=jan13problems上下载，还可以看到题解（不过是英文的:-D）
PS3:如果有翻译的问题或题目的不理解，可以在问答后面留言的说。
思路：
这是当年的官方思路：
If we knew the area Bessie was going to paint were small, this would be easy; we could just explicitly keep track of how many coats of paint each unit of fence had. Unfortunately, we don't.
But...Bessie only stops on at most 100,001 different points (one per move). So these are the only "interesting coordinates". In particular, any two points between two "interesting coordinates" will have the same number of coats of paint (this idea is a generally useful trick called "coordinate compression", and it's worth knowing). So it's enough to keep track of the number of coats of paint along each of these 100,002 segments.
This still might not be fast enough; each move could cover all 100,002 segments, so this algorithm still looks quadratic. So we can apply another useful trick, which is just keeping track of the deltas introduced by each of Bessie's moves. Each of Bessie's moves is a segment (on our coordinate-compressed line), and at the beginning of the segment we write down "+1 coats of paint" and at the end of the segment we write down "-1 coats of paint". Then if we scan from left to right, we can add up the deltas as we go, and keep track of the number of coats on each segment.
This gives an O(n lg n) solution (to "scan from left to right", we need to sort the segments). It was a bit of a winding logical path to get here, so the final solution may not be quite clear. Take a look at Travis Hance's solution, which presents the idea quite elegantly: (and remember coordinate compression and deltas-for-segments for later!)
看不懂是吧，我英语不好，也看不懂。所以用了差分+离散化搞了一下。
#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; map<int,int>F; int q[300000],top; int n,m,now,ans; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ char c;int x; scanf("%d",&x); cin>>c; if(c=='R'){ q[++top]=now; F[q[top]]++; q[++top]=now+x; F[q[top]]--; now+=x; }else{ q[++top]=now-x; F[q[top]]++; q[++top]=now; F[q[top]]--; now-=x; } } sort(q+1,q+top+1); now=F[q[1]]; for(int i=2;i<=top;i++) if(q[i]!=q[i-1]){ if(now>=m) ans+=q[i]-q[i-1]; now+=F[q[i]]; } printf("%d",ans); }