ICPC 2018 徐州网络预赛 G Trace

【题目链接】

样例输入
3
1 4
4 1
3 3
样例输出
10

解题思路

It’s guaranteed that a wave will not cover the other completely.
题目保证了不完全覆盖，并且保证x1<=x2与y1<=y2不同时成立，所以大大简化难度。
首先考虑n==2的情况，假设第二个点（x2,y2）已经画在坐标上了，然后第一个点（x1,y1）两种情况
1.如果x1 < x2，那么y1 > y2，那么ans += x1+y1-y2;
2.如果x1 > x2，那么y1 < y2，那么ans += y1+x1-x2;
将x y分开看可以发现如果x是当前出现过的最小值，ans直接加上x，反之，ans加上x后再减去比x小的值，y同理。


推广到n>2的话，从后往前遍历，如果x是当前出现过的最小值，ans直接加上x，反之，ans加上x后再减去比x小的最大值，y同理。

注意一个小细节

代码22行与29行，需要vx.lower_bound()，不能用lower_bound(vx.begin(),vy.begin,)，实测第二个会超时，可能是因为内部实现不同吧。。。

AC代码

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
struct node
{
    int a;
    int b;
}que[100005];
int main()
{
    set<int>vx, vy;
    int n;
    long long ans = 0;
    int maxx = 0;
    int maxy = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &que[i].a, &que[i].b);
    for (int i = n - 1; i >= 0; i--)
    {
        set<int>::iterator it = vx.lower_bound(que[i].a);
        if (it != vx.begin())
            ans += que[i].a - *(--it);
        else
            ans += que[i].a;
        vx.insert(que[i].a);

        set<int>::iterator itit = vy.lower_bound(que[i].b);
        if (itit != vy.begin())
            ans += que[i].b - *(--itit);
        else
            ans += que[i].b;
        vy.insert(que[i].b);
    }
    printf("%lld\n", ans);
}