怎么用PS做网站横幅,爱站网长尾关键词,做ppt图表的网站,wordpress防止图片被采集弗拉德找到了一个由 n 个整数组成的数组 a #xff0c;并决定按不递减的顺序排序。
为此#xff0c;弗拉德可以多次执行下面的操作#xff1a;
提取数组的第一个元素并将其插入末尾#xff1b; 将个元素与前一个元素对调#xff0c;直到它变成第一个元素或严格大于前一个…弗拉德找到了一个由 n 个整数组成的数组 a 并决定按不递减的顺序排序。
为此弗拉德可以多次执行下面的操作
提取数组的第一个元素并将其插入末尾 将个元素与前一个元素对调直到它变成第一个元素或严格大于前一个元素。 请注意这两个操作都是操作的一部分对于一个操作必须同时应用这两个操作。
例如如果对数组 [ 4,3,1,2,6,4 ]进行操作它将发生如下变化
[ 4,3,1,2,6,4 ]; [ 3,1,2,6,4,4 ]; [ 3,1,2,6,4,4 ]; [ 3,1,2,4,6,4 ]. 弗拉德没有时间进行所有的操作所以他要求你确定对数组进行排序所需的最少操作数或者报告说这是不可能的。
输入 输入的第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t ( 1≤t≤10^4 ) t(1≤t≤104) - 测试用例的数量。测试用例说明如下。
每个测试用例的第一行包含一个整数 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n ( 1≤n≤2⋅10^5 ) n(1≤n≤2⋅105) - 数组的长度。
每个测试用例的第二行包含 n n n 个整数 a 1 , a 2 , a 3 , … , a n ( 1 ≤ a i ≤ 1 0 9 ) a_1,a_2,a_3,…,a_n ( 1≤a_i≤10^9 ) a1,a2,a3,…,an(1≤ai≤109) - 数组的元素。
保证所有测试用例中 n n n 的总和不超过 2 ⋅ 1 0 5 2⋅10^5 2⋅105 。
输出 对于每个测试用例输出一个整数 - 对数组进行排序所需的最少操作数。如果无法排序则输出 −1 作为答案。 首先我们可以找到这一序列的最小值那么可以得知最小值前面的数一定都要被移动因为要保持数列是不递减顺序。
那么如果前面的数都移动结束之后我们就不能再移动了因为最小值一定不会严格小于任何数所以就会陷入死循环所以可以知道如果最小值后面的序列原本如果是递减序的话那么就没有可能将其正常排序了因为最小值前面的数移动到后面去不会影响后面原本的顺序。 CODE
#includebits/stdc.h
using namespace std;
const int N 2e510;
#define endl \nint a[N];void solve(){int n;cin n;int mm 1;for(int i 1;i n;i){cin a[i];if(a[i] a[mm])mm i;}for(int i mm;i1 n;i){if(a[i] a[i1]){cout -1 endl;return;}}cout mm-1 endl;
}int main(){int T;cin T;while(T--){solve();}return 0;
}我会用MARKDOWN颜色了哈哈哈
