逆向 - 2019.11.8 波浪

题面

【问题描述】

在第一象限里，有一个海滩上时不时有波浪。一个波浪用一个数字对 \((x, y)\) 表示，代表一个顶点为 \((0,0)\)，\((x,0)\)，\((0,y)\)，\((x,y)\) 的矩形。

每一个波浪会冲刷掉其范围内的其他波浪留下的痕迹，并保持自己的痕迹 \((x,0)\to(x,y)\) 和 \((0,y)\to(x,y)\)。

现在海岸上的人想知道 \(n\) 波后海岸上的痕迹总长度。输入数据保证一个波浪不会完全覆盖另一个波浪。

【输入文件】

第一行是波浪的数量 \(n\)（\(n \le 50000\)）。

下面为 \(n\) 行，每行包含两个数字 \((x,y)\)，（\(0 < x,y \le 10000000\)）表示每一个波浪。

【输出文件】

单行输出答案。

【输入样例】

3
1 4
4 1
3 3

【输出样例】

10

解

按题目方向计算，对以后的波浪有后效性。逆向计算，则每次处理到的波浪，把它的痕迹冲掉的波浪都确定了。不难发现，每一次增加一个新的波浪，它被遮住的部分就是他的 \((x,y)\) 中，\(x\) 在 \(\{x\}\) 中的前驱和 \(y\) 在 \(\{y\}\) 中的前驱。但是，如果一个 \(x\) 比先前所有的 \(x\) 都小，前驱应为0。必须在全部操作之前插入 0 元素。

如果用 std::vector 存储已经加入的波浪，插入费时。可以用 std::set 来组织坐标。

程序

#include <iostream>
#include <set>
#include <cstdio>
using namespace std;
 
#define MAXN 50050
int n, x[MAXN], y[MAXN];
set<int> xs, ys;
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
     
    xs.insert(0); ys.insert(0);
    int ans = 0;
    for (int i = n - 1; i > -1; i--) {
        set<int>::iterator ix = xs.lower_bound(x[i]);
        set<int>::iterator iy = ys.lower_bound(y[i]);
        ix--; iy--;
        ans += x[i] - (*ix) + y[i] - (*iy);
        xs.insert(x[i]);
        ys.insert(y[i]);
    }
     
    cout << ans << endl;
    return 0;
}

逆向 - 2019.11.8 波浪

原文：https://www.cnblogs.com/lrw04/p/11826387.html