首页 > 代码库 > CSU-1401: 插入排序
CSU-1401: 插入排序
Description
每次选择序列最左边的数,然后将其插入到序列中任意一个位置。求至少需要重复进行多少次上述操作,才可以将序列变为一个递增序列。
Input
输入的第一行包含一个整数T (T > 0),表示一共有T组测试数据.
对于每组测试数据,第一行包含一个整数n (1 ≤n ≤ 105),表示这个序列中一共有n个整数。第二行包含n个各不相同的整数(这些整数均在[1, 109]范围内),依次描述了这个序列中的各个数。
Output
对于每组测试数据,输出一个整数,表示至少需要重复进行多少次上述操作,才可以将这个序列变为一个递增序列。
Sample Input
3
3
1 2 3
3
1 3 2
5
1 5 4 3 2
Sample Output
0
2
4
HINT
Source
中南大学第八届大学生程序设计竞赛热身赛
//设m为以最后一个数结尾的连续的上升序列的长度。答案就是n-m。
例如:求m:如果是1 5 2 3 4,就是3 。 3,2,1就是1。
因为你只能最左边的数移动那么最优策略就是保持我说的最靠右的那段上升子列不动剩下的每个数动一下就行了。
#include<cstdio> inta[100005]; intmain() { intt,n,i,j,ans; scanf("%d",&t); while(t--) { ans=1; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); for(j=n-2;j>=0;j--) { if(a[j]<a[j+1]) ans++; else break; } printf("%d\n",n-ans); } return0; }
CSU-1401: 插入排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。