Description
You are given a sequence $ a $ consisting of $ n $ integers $ a_1, a_2, dots, a_n $ , and an integer $ x $ . Your task is to make the sequence $ a $ sorted (it is considered sorted if the condition $ a_1 le a_2 le a_3 le dots le a_n $ holds).
To make the sequence sorted, you may perform the following operation any number of times you want (possibly zero): choose an integer $ i $ such that $ 1 le i le n $ and $ a_i > x $ , and swap the values of $ a_i $ and $ x $ .
For example, if $ a = [0, 2, 3, 5, 4] $ , $ x = 1 $ , the following sequence of operations is possible:
1. choose $ i = 2 $ (it is possible since $ a_2 > x $ ), then $ a = [0, 1, 3, 5, 4] $ , $ x = 2 $ ;
2. choose $ i = 3 $ (it is possible since $ a_3 > x $ ), then $ a = [0, 1, 2, 5, 4] $ , $ x = 3 $ ;
3. choose $ i = 4 $ (it is possible since $ a_4 > x $ ), then $ a = [0, 1, 2, 3, 4] $ , $ x = 5 $ .
Calculate the minimum number of operations you have to perform so that $ a $ becomes sorted, or report that it is impossible.
Solution
假设已经把$x$加入数列，对这个数列排序会得到最终的结果
发现将$x$插入数列相当于将数列中的一端向右移动一段，从前到后扫数组，当新数组小于原数组对应位时选择交换，每扫一位检查序列单调性
#include<algorithm> #include<iostream> #include<cstdio> using namespace std; int n,x,a[505],sav[505],ans; bool tag; inline int read() { int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } bool check(int pos) { bool ret=true; for(int i=pos;i<n;i++) if(a[i]>a[i+1]) ret=false; return ret; } int main() { for(int t=read();t;t--) { n=read(),x=read(),tag=false,ans=0; for(int i=1;i<=n;i++) sav[i]=a[i]=read(); for(int i=1;i<n;i++) if(a[i]>a[i+1]) tag=true; if(!tag) { puts("0");continue; } sav[n+1]=x,sort(sav+1,sav+n+2),tag=false; for(int i=1;i<=n;i++) { if(a[i]!=sav[i]) if(a[i]>sav[i]) swap(x,a[i]),++ans; else tag=true; if(a[i]<a[i-1]) tag=true; if(check(i)) break; } if(tag) puts("-1"); else printf("%d ",ans); } return 0; }