洛谷 P2205 [USACO13JAN]画栅栏

这题其实没什么，但用到的算法都十分有用。做一个不恰当的比喻，这是一只必须用牛刀杀的鸡，但因为我这个蒟蒻杀不死牛，所以只能找只鸡来练练手。

题目描述

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\n",ans);
    return 0;
}