NC247405. 惊鹊
描述
输入描述
第一行数据组数,代表共有组数据。
对于每组数据,第一行,代表排列长度。第二行个数字,代表排列。保证给出的是合法排列。
,,
输出描述
对于每组数据,输出一行个整数,代表排列。若有多个可以使得最小的,任意输出一个即可。
示例1
输入:
2 3 1 2 3 2 2 1
输出:
1 2 3 1 2
说明:
对于第一组样例,有,故前缀最值变化次数为,为最小的。pypy3 解法, 执行用时: 1194ms, 内存消耗: 102808K, 提交时间: 2022-12-25 14:23:39
T=int(input()) for t in range(T): n=int(input()) if n==1: ff=int(input()) print(1) else: li=list(map(int,input().split())) li=li k=list(range(0,n)) if li[0]!=1: k[li[0]-1],k[0]=k[0],k[li[0]-1] k[0],k[1]=k[1],k[0] for i in range(n): k[i]+=1 print(*k)
C++(clang++ 11.0.1) 解法, 执行用时: 510ms, 内存消耗: 15548K, 提交时间: 2022-12-27 16:24:22
#include<iostream> using namespace std; const int N=5e5+5; int ar[N]; int main(void) { int t; cin>>t; while(t--) { int n; cin>>n; for(int i=1;i<=n;i++) cin>>ar[i]; int cnt=1; for(int i=1;i<=n;i++) { if(ar[1]==i) cout<<"1 "; else cout<<++cnt<<" "; } cout<<"\n"; } return 0; }
C++(g++ 7.5.0) 解法, 执行用时: 520ms, 内存消耗: 8900K, 提交时间: 2023-01-01 14:15:46
#include<bits/stdc++.h> using namespace std; int a[2000000]; int main() { int n,t; for(cin>>t; t; t--) { cin>>n; for(int i=1; i<=n; i++)cin>>a[i]; int cnt=2; for(int i=1; i<=n; i++) { if(i==a[1]) cout<<1<<" "; else cout<<cnt++<<" "; } cout<<endl; } }