题解 B3694 数列离散化

link

简而言之，离散化就是把一个数列转化为由小到大的排名来缩小范围。

离散化需要这个题不用数字本身。

举个例子：

-2002 448799 1 49932 35793

离散化后就是：

1 5 2 4 3

\(-2002\) 最小，所以它对应 \(1\)

\(448799\) 最大，所以它对应 \(5\)

实现

考虑如何实现。

首先由于离散化前后数的顺序不能发生变化，我们需要复制一份：

for (int i = 1; i <= n; ++i) c[i] = a[i];

然后需要排序来确定顺序：

sort (a + 1, a + n + 1);

最后在 \(C\) 数组中找每个 \(a_i\) 就能确定第 \(i\) 个数的离散化结果了。

for (int i = 1; i <= n; ++i) {
    rank[i] = lower_bound(c + 1, c + n + 1) - c;
}

注意这里为什么不减 (c + 1)：题目说 ：

定义 \(\mathrm{rank(i)}\) 表示数列 \(a\) 中比 \(a_i\) 小的不同数字个数再加一。

所以减去的应少 \(1\)​。

而且由于

lower_bound( begin,end,num)：从数组的begin位置到end - 1位置二分查找第一个大于等于num的数字，找到返回该数字的地址，不存在则返回end。

则如果某个数不止 \(1\) 个，则 lower_bound 返回的是最后一个的地址，然而我们想要的是第一个。

于是我们就需要去重。

unique 即可。

int cnt = unique(c + 1, c + n + 1) - (c + 1);

于是在 lower_bound 时就需要lower_bound(c + 1, c + cnt + 1)而不是 lower_bound(c + 1, c + n + 1)

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n;
int a[N];
int c[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; 
        c[i] = a[i];
    }
    sort (c + 1, c + n + 1);
    int cnt = unique(c + 1, c + n + 1) - (c + 1);
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(c + 1, c + cnt + 1, a[i]) - c;
    }
    for (int i = 1; i <= n; ++i) cout << a[i] << " "; //不是 c[i]!!!
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    int T; cin >> T; while (T --) solve();
    return 0;
}