模拟 + 贪心

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e5 + 10;

int a[N];
int st1[N];  //存放0的下标
int st2[N];  //存放使用过的数
int main()
{
    int T;
    scanf("%d", &T);;
    while( T -- )
    {
        int n;
        scanf("%d", &n);

        for (int i = 1; i <= n + 1; i ++ )
        {
             st1[i] = -1;st2[i] = -1;
        }

        for (int i = 1; i <= n; i ++ )
        {
            scanf("%d", &a[i]);
            if(a[i] == 0)
            {
                st1[i] = 1;
            }
            else
            {
                st2[a[i]] = 1;
            }
        }

        queue<int> q1, q2;
        for (int i = 1; i <= n; i ++ )
        {
            if(st1[i] == 1) 
            {
                q1.push(i);      //用队列存放a[i] == 0的下标 i 这跟队列显然是单调递增
            }
            if(st2[i] == -1 && st1[i] == 1)
            {
                 q2.push(i);     // 现存一部分 i 即 原数组值没有出现过 并且 a[i] == 0
                 st2[i] = 1;
            }
        }
        for (int i = 1; i <= n; i ++ )
        {
            if(st2[i] == -1) q2.push(i);  //再存一部分 i 即 原数组值没有出现过 但是 a[i] != 0
        }


        // 因为队列是先进先出的 所以这里我们给q1里的元素配对 要优先选用 q2里先存的一部分 数
        // 这里用到了贪心的思想 不然下边俩个队列可能出现死循环

        //拿样例1来举例说明  如果我们的q2不按照 上述 分步 来存的话 q1 q2 队列里的元素如下所示
        // q1 = { 2 , 3 }
        // q2 = { 1 , 3 }

        // 这种情况我们遍历q1里的元素给其 配对 时  第一次遍历 a[2] = 1, 
        // 此时 q1 = { 3 }
        //      q2 = { 3 }
        // 陷入死循环 其实我们可以 让 a[2] = 3, a[3] = 1 的 
        // 所以我们 上述往q2 里 存入数据的时候 要 优先 存 a[i] == 0 即 i 即在q1里出现 也在q2里出现
        //  这样我们给 q1 里的 元素 配对的时候 就 一定 不会 出现 死循环 因为 此题保证有解 所以我们
         // 在每一步 给 q1 里的元素配对时 采用贪心的思想 局部最优化处理 就一定能找到一个解

        while(!q1.empty())
        {
            int x = q1.front();
            q1.pop();
            while(!q2.empty())
            {
                int y = q2.front();
                q2.pop();
                if(x != y)
                {
                    a[x] = y;
                    break;
                }
                else q2.push(y);
            }
        }


        for (int i = 1; i <= n; i ++ ) printf("%d ",a[i]);
        puts("");

    }

    return 0;
}