排序与离散化CSP-J

💡 核心思想

排序是将数据按特定顺序排列的操作，是算法竞赛的基础工具。离散化是将大范围的数值映射到紧凑的小范围，常用于坐标压缩，是处理大数据范围的重要技巧。

🎯 直觉理解

排序就像整理书架上的书——按作者名排序。离散化就像把"第1排第1000000000列"简化为"第3个位置"——重要的不是绝对位置，而是相对顺序。

📝 算法流程

1. 排序：使用 STL sort()，自定义比较函数
2. 离散化：排序 → 去重 → 二分查找映射
3. 注意 stable_sort() 保证相等元素原有顺序

$$\text{离散化：} a_i \mapsto \text{rank}(a_i) = \text{lower_bound(sorted, } a_i) - sorted.begin() + 1$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 排序 + 离散化模板
int main() {
    int n; cin >> n;
    vector<int> a(n), b;
    for (auto& x : a) cin >> x;
    b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end()); // 去重
    // 离散化：a[i] 映射为 1-based rank
    for (auto& x : a) {
        x = lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
    }
    for (auto x : a) cout << x << ' ';
    return 0;
}

⚠️ 常见坑点

📚 相关题目