题目

编写程序，阐述 std::unique 的真实行为：验证其仅能去除“相邻的重复元素”，因此在去重前必须预先对容器进行 std::sort 排序。随后利用 sort + unique + erase + lower_bound 构建算法竞赛与工程几何中极其关键的“坐标离散化”（Coordinate Discretization）预处理流水线，将大范围稠密/稀疏坐标值映射为紧凑的整数排名下标。

输入格式：无需外部输入。

输出格式：输出原始极大值坐标、离散化去重结果与映射后的压缩排名索引。

数据范围与约定：坐标离散化、相邻去重与二分投影。

思路与算法

1. unique 的相邻性陷阱
如果数组是 {1, 2, 1}，调用 unique 毫无作用，因为两个 1 不相邻！必须先 std::sort 将所有相同元素聚拢，然后再调用 unique。

2. 离散化的应用背景
当坐标数值很大（如 \(x \in [-10^9, 10^9]\)），无法直接建立数组当下标；若只关心相对大小关系，将其保序离散化映射到 \([0, N-1]\) 可以大幅降低空间占用。

3. lower_bound 寻址映射
完成 sort + unique + erase 后的序列严格单调递增，查询原数字 \(x\) 映射后的编号只需执行 std::lower_bound(v.begin(), v.end(), x) - v.begin()。

完整程序

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 原始具有极大跨度与重复项的坐标列表
    std::vector<int> coords = {1000000000, -500, 42, -500, 1000000000, 0, 42};

    std::cout << "原始离散坐标集合: ";
    for (int x : coords) std::cout << x << " ";
    std::cout << "\n";

    // 1. 拷贝并构建纯净且去重的保序基准表
    std::vector<int> discreteTable = coords;

    // 关键第一步：必须先排序将重复项聚拢到相邻位置
    std::sort(discreteTable.begin(), discreteTable.end());

    // 关键第二步：调用 unique 消除相邻重复项，并截断多余尾部
    discreteTable.erase(
        std::unique(discreteTable.begin(), discreteTable.end()),
        discreteTable.end()
    );

    std::cout << "排序去重后的映射基准表: ";
    for (int x : discreteTable) std::cout << x << " ";
    std::cout << " (基准元素数: " << discreteTable.size() << ")\n\n";

    // 2. 将原序列中的每个大数投影转换为离散紧凑下标 [0, K-1]
    std::cout << "--- 原始坐标在离散表中的紧凑下标映射结果 ---\n";
    for (int x : coords) {
        auto it = std::lower_bound(discreteTable.begin(), discreteTable.end(), x);
        int rankIndex = std::distance(discreteTable.begin(), it);
        std::cout << "坐标 " << x << " -> 离散编号: [" << rankIndex << "]\n";
    }

    return 0;
}

运行示例

输出：

原始离散坐标集合: 1000000000 -500 42 -500 1000000000 0 42 
排序去重后的映射基准表: -500 0 42 1000000000  (基准元素数: 4)

--- 原始坐标在离散表中的紧凑下标映射结果 ---
坐标 1000000000 -> 离散编号: [3]
坐标 -500 -> 离散编号: [0]
坐标 42 -> 离散编号: [2]
坐标 -500 -> 离散编号: [0]
坐标 1000000000 -> 离散编号: [3]
坐标 0 -> 离散编号: [1]
坐标 42 -> 离散编号: [2]