CF1741BFunnyPermutation题解-创新互联

输入一个整数 n n n，要求构造一个长度为 n n n 的排列 p p p， p i ∈ [ 1 , n ] p_i \in [1,n] pi​∈[1,n]，并同时满足以下两点要求:

• 对于排列中的每一个元素，满足在和它相邻的元素中至少有一个元素和它的值相差 1 1 1。
• 下标从 1 1 1 开始，每个下标对应的元素不能和下标相等，形式化的，对于每一个 i ∈ [ 1 , n ] i \in [1,n] i∈[1,n] 都必须满足 p i ≠ i p_i \neq i pi​=i。

如果可以构造，输出构造的排列。
如果不可以，输出 − 1 -1 −1。

构造题，首先考虑第一个要求，先想到的就是按顺序排列，但是为了满足各个下标对应元素不能和下标相等，再考虑顺序移动一位，后边的补到前边，但这样就会导致最前边的元素无法满足第一个要求，所以整体向后顺序移动两位，溢出的部分补到前边。

要注意的是，顺序向后移动两位之后还要保证剩下的部分也满足第一个条件，因此这样的操作只适用于 n ≥ 4 n \geq 4 n≥4 的情况，那么对于 n = 1 , 2 , 3 n={1,2,3} n=1,2,3 的情况我们可以特判一下。

因此，下面代码中的 check 函数我只判断了是否满足第二个要求。

形式化的，对于 n ≥ 4 n \geq 4 n≥4的情况，我们在要构造的排列中先放入 n − 1 n-1 n−1 和 n n n，然后依次放入 1 1 1 到 n − 2 n-2 n−2 即可。

#includeusing namespace std;

inline long long read()
{long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {if (ch == '-')
        {f = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch))
    {x = (x<< 1) + (x<< 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

bool check(vector&v)
{for (ll i = 0; i< v.size(); i++)
    {if (v[i] == i + 1)
        {return false;
        }
    }
    return true;
}

void solution()
{ll n = 0;
    n = read();

    if (n == 1)
    {cout<< -1<< endl;
        return;
    }
    if (n == 2)
    {cout<< 2<< ' '<< 1<< endl;
        return;
    }
    if (n == 3)
    {cout<< -1<< endl;
        return;
    }
    vectornums;
    nums.push_back(n - 1);
    nums.push_back(n);
    for (ll i = 1; i<= n - 2; ++i)
    {nums.push_back(i);
    }
    if (check(nums))
    {for (ll i = 0; i< nums.size(); i++)
        {cout<< nums[i]<< " ";
        }
        cout<< endl;
    }
    else
    {cout<< -1<< endl;
    }
}

int main()
{ll T = 0;
    T = read();
    for (ll i = 0; i< T; i++)
    {solution();
    }

    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧