NC200616. K-钟Sir的任务
描述
输入描述
第一行是一个整数t(1<=t<=100)，表示游戏场数。
接下来对每场游戏有两行描述，
第一行是一个整数n（1<=n<=100），表示排列的长度，
第二行包含n个整数,表示给定的1~n的一个排列。
输出描述
输出在不违反游戏规则的前提下，能够得到的字典序最小的排列。
示例1
输入:
4 5 5 4 1 3 2 4 1 2 4 3 1 1 4 4 3 2 1
输出:
1 5 2 4 3 1 2 3 4 1 1 4 3 2
说明:
教练试玩第一场游戏后,建议你这样操作C(clang 3.9) 解法, 执行用时: 6ms, 内存消耗: 372K, 提交时间: 2019-12-29 13:21:48
#include"stdio.h"
int main(){
int T,n,a[105];
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
int p,w=0,w1=0;
while(w<n){
p=n;
for(int i=w;i<n;i++){
if(a[i]<p){
p=a[i];
w=i;
}
}
for(int j=w;j>w1&&a[j]<a[j-1];j--){
int t=a[j];
a[j]=a[j-1];
a[j-1]=t;
}
w1=w;
w++;
}
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
}
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2020-07-17 14:35:16
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,f,n,T,a[105],V[105];
scanf("%d",&T);
while(T--)
{
scanf("%d",&n),f=1;
for(i=0;i<n;i++)scanf("%d",&a[i]),V[i]=0;
while(f)
{
f=0;
for(i=n-1;!f&&i>0;i--)if(!V[i]&&a[i]<a[i-1])V[i]=1,swap(a[i],a[i-1]),f=1;
}
for(i=0;i<n;i++)printf("%d ",a[i]);
printf("\n");
}
}