列表

详情


NC247405. 惊鹊

描述

对于长度为n的排列P,定义f(P)P的前缀最小值变化次数(即满足如下条件的i的个数:)。

现在给定排列P,请构造一个排列Q,使得max(f(Q),f(Q'))尽量小。其中

输入描述

第一行数据组数T,代表共有T组数据。

对于每组数据,第一行n,代表排列长度。第二行n个数字,代表排列P。保证给出的是合法排列。

,,

输出描述

对于每组数据,输出一行n个整数,代表排列Q。若有多个可以使得max(f(Q),f(Q'))最小的Q,任意输出一个即可。

示例1

输入:

2
3
1 2 3
2
2 1

输出:

1 2 3
1 2

说明:

对于第一组样例,有Q=Q',故Q=\{1,2,3\}前缀最值变化次数为1,为最小的。

对于第二组样例Q=\{1,2\} , Q' = \{Q_{P_{1}},Q_{P_{2}}\} = \{Q_{2},Q_{1}\} = \{2,1\},f(Q)=1,f(Q')=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;
	}

}

上一题