大连大学2022年11月程序设计竞赛（同步赛） 原创D题题解

题目描述

给定一个数组a，长度为n，这是一个首尾相接的数组 (a1​前面是 an,an​后面是a1​)

如果从某一个位置开始(计入b数组)，走n−1步。

把走过的数依次放进新数组b，如果能构成一个单调不减的大小为n的数组，输出这个数组，否则输出“-1”。
请注意，本题只能向后走。且an的后面是a1的后面是a2​，依此类推。

输入描述:

第一行输入一个整数t(1≤t≤1000)，表示样例的数量。
接下来的每t组数据，第一行为一个整数n(1≤n≤2⋅10^5)，表示a数组的大小。
第二行为n个整数，表示为a数组(1≤a≤2⋅10^5)。
所有样例的n的总和不超过10^6。

输出描述:

输出t行，每行n个整数或“-1”。

示例1

输入

2
5
3 4 5 1 2
6
4 4 2 2 3 3

输出

1 2 3 4 5
2 2 3 3 4 4

以下为本人的题解：

这道题目用排序+双指针能很快的做出来

但是注意不用走就能通过的同时要特判以下

#include<bits/stdc++.h>
using namespace std;

const int N=200020;

int t;
int main()
{
     cin >> t;
     while(t--)
     {
         int n,cnt=0,a[N];
         cin >> n;
         for(int i=1;i<=n;i++)
         {
             cin >> a[i];
         }
         for(int i=1;i<=n-1;i++)
         {
             if(a[i]>a[i+1])
             cnt++;    
         }
         
         if((cnt==1 && a[n]<=a[1] )|| cnt==0)
         {
             sort(a+1,a+1+n);
             for(int i=1;i<=n;i++)
             cout<<a[i]<<" ";
             
             cout<<endl;
         }
         else
         cout<<"-1"<<endl;
     }
     return 0;
}