这题其实没什么，但用到的算法都十分有用。做一个不恰当的比喻，这是一只必须用牛刀杀的鸡，但因为我这个蒟蒻杀不死牛，所以只能找只鸡来练练手。
题目描述
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层涂料的栅栏数
好像一眼就能看出离散化，但我这个蒟蒻之前并没有太多的了解扫描线。
思路：离散化扫描。
把一条线段的两个端点存下来，左边那个点的值是+1，右边是-1。之后按距离排序。
然后开始扫描，每扫到一个点就加上它的值到sum里，如果有时候sum>=k，那么ans加上这条线段的长度（这个一会儿看注释）
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; struct node{ int x,v; }w[400001]; char c; int n,l,i,k,ans,cnt; inline bool cmp(node a,node b){ return a.x<b.x; } int main(){ int x; scanf("%d%d",&n,&k); for (i=0; i<n; i++){ scanf("%d %c",&x,&c); if (c=='R'){ w[++cnt].x=l; w[cnt].v=1; w[++cnt].x=l+x; w[cnt].v=-1; l+=x; } else{ w[++cnt].x=l; w[cnt].v=-1; w[++cnt].x=l-x; w[cnt].v=1; l-=x; } } sort(w+1,w+cnt+1,cmp); l=w[1].v; for (i=2; i<=cnt; i++){ if (l>=k){ ans+=w[i].x-w[i-1].x;//就是这里，如果l>=k那么一定是前面一段线段染色次数超过了k，所以我的顺序是这样的 } l+=w[i].v; } printf("%d ",ans); return 0; }