time limit per test1.5 seconds memory limit per test512 megabytes inputstandard input outputstandard output
Example
input
6 4 1 2 3 5 4 5 6 1 1 3 4 4 1 10 2 2 10 11 9 2 10 12 11 5 18 81 324 218 413 324
output
3 0 0 -1 1 3
首先找到不满足非递减的位置的元素，然后考虑将这个数换掉，但是问题是换掉这个数要满足a[i] > x;这样一来，就需要找到找到这样一个满足条件的位置，并记录在pos中，然后从满足条件的 pos往后到 i - 1的部分进行交换，每交换一次就讲记录答案的ans加一，然后判断是不是满足非递减的情况，如果满足的时候，输出ans,不满足的时候直接输出 -1
在中途的时候可以优化一下下，如果说交换了一波时候还没有满足a[i] >= a[i-1];就直接记录下，最后输出 -1
int a[maxn]; int main() { int _ = read; while(_--){ int n = read,x=read; for(itn i=1;i<=n;i++) cin >> a[i]; int flag = 1; int ans = 0; for(int i=2;i<=n;i++){ int pos = 0; if(a[i] < a[i-1]){ for(int j=1;j<=i-1;j++){ if(a[j] > x){ pos = j;///get the right position break; } } if(pos == 0) break; for(int j=pos;j<=i-1;j++){ if(a[j] > x){/// swap the two numbers swap(x,a[j]); ans ++; } } if(a[i] < a[i-1]){/// output -1 flag = 0; break; } } } if(flag == 0){ puts("-1"); continue; } for(int i=1;i<n;i++){ if(a[i] > a[i+1]){ flag = 0; break; } } if(flag) cout << ans <<endl; else puts("-1"); } return 0; }
