ACM-ICPC 2018 徐州赛区网络预赛 G. Trace

题意

后浪推前浪，每个浪是一个矩形，由两条边组成，后形成的浪会把之前浪的边吞掉，问最后剩下的边的总长度。

思路

越后生成的浪保留的边越多，所以我们反过来放就保证我们先放的不会被吞，采用集合存放点，每次放新的点的时候查找到他正左端的点和正右端的点，在ans上加上横纵坐标之差就完成了。

题目保证没有任两个浪相互包含，这使得我们这样的算法总是合理的。

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=5e4+7;
PII point[N];
int main()
{
    set<PII> se;
    int n;
    scanf("%d",&n);
    for(int i=0,a,b;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        point[i] = make_pair(a,b);
    }
    long long ans=point[n-1].first+point[n-1].second;
    se.insert(make_pair(0,1e7+5));
    se.insert(make_pair(1e7+5,0));
    se.insert(point[n-1]);
    for(int i=n-2;i>=0;i--)
    {
        auto it=se.lower_bound(point[i]);
        ans+=point[i].second-it->second;
        it--;
        ans+=point[i].first-it->first;
        se.insert(point[i]);
    }
    printf("%lld
",ans);
}