TB椰程 TypeBuddy 打字搭子

离散化

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 555 字

大坐标压成小下标，排序去重后二分映射

  • 算法
  • 离散化

前置内容

正文

// 离散化：把大坐标压成小下标
// 只关心相对大小，不关心具体值
// 排序去重后用二分映射
// 例：把稀疏坐标映射到 1..m
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100005], b[100005], n, m;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        // 副本用于排序去重
        b[i] = a[i];
    }
    // 排序 + 去重
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b - 1;
    // 二分查排名
    for (int i = 1; i <= n; i++) {
        int r = lower_bound(
            b + 1, b + m + 1, a[i]) - b;
        printf("%d ", r);
    }
    return 0;
}

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK