两个序列按序离散化
da_AA
2018-06-01 20:32:01
## 问题
考虑这样一个问题：有两个序列，例如：
> 3 6 7 4 8
> 5 2 3 6 7
将第二个序列变成按第一个序列的顺序排列，即：
> 2 5 6 3 7
如果看下标，则序列二变为：
> 2 1 4 3 5
求这个数组。
## 算法
将序列A, B中每个数“绑定”其下标：
```c++
struct num {
int val, idx;
};
num A[N], B[N];
```
| A | B |
| :----------: | :----------: |
| (3,1) | (5,1) |
| (6,2) | (2,2) |
| (7,3) | (3,3) |
| (4,4) | (6,4) |
| (8,5) | (7,5) |
将A, B序列分别按值排序：
| A | B |
| :----------: | :----------: |
| (3,1) | (2,2) |
| (4,4) | (3,3) |
| (6,2) | (5,1) |
| (7,3) | (6,4) |
| (8,5) | (7,5) |
现在，两个数组就有序了，而$A[1].idx$为1,$B[1].idx$为2，所以，A数组的一号位对应着B数组的二号位，同理，A数组的四号位对应着B数组的三号位，A数组的二号位对应着B数组的一号位……
所以：
```cpp
c[a[i].idx] = b[i].idx;
```
c数组即为所求。