P76014 礼物回执 — 题解

专题： 模拟与枚举
适用题目： 新生 OJ 本地题包中的 P76014，不要直接用于外站同名题。

解题思路

若第 i 人送给 a[i]，就在答案数组中设置 ans[a[i]] = i。

复杂度

时间 $O(n)$，空间 $O(n)$。

易错点

这是求排列的逆映射，索引从 1 开始最方便。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int n; scanf("%d",&n); int *from = calloc(n+1,sizeof(int));
    for (int i = 1; i <= n; i++) {int to; scanf("%d",&to); from[to] = i;}
    for (int i = 1; i <= n; i++) printf("%d%c",from[i], i==n?'\n':' ');
    free(from);
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int> x(n+1);
    for(int i=1;i<=n;i++){
        int y;
        cin>>y;
        x[y]=i;
    }
    for(int i=1;i<=n;i++)cout<<x[i]<<(i==n?'\n':' ');
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。