csu1041-白红宇的个人博客

csu1041

发布日期：2021-06-29 10:50:30 浏览次数：2 分类：技术文章

本文共 827 字，大约阅读时间需要 2 分钟。

1401: 插入排序

Time Limit: 1 Sec

Memory Limit: 128 MB

Submit: 279

Solved: 142

[ ][ ][ ]

Description

每次选择序列最左边的数，然后将其插入到序列中任意一个位置。求至少需要重复进行多少次上述操作，才可以将序列变为一个递增序列。

Input

输入的第一行包含一个整数T (T > 0)，表示一共有T组测试数据.

对于每组测试数据，第一行包含一个整数n (1 ≤ n ≤ 105)，表示这个序列中一共有n个整数。第二行包含n个各不相同的整数（这些整数均在[1, 109]范围内），依次描述了这个序列中的各个数。

Output

对于每组测试数据，输出一个整数，表示至少需要重复进行多少次上述操作，才可以将这个序列变为一个递增序列。

Sample Input

331 2 331 3 251 5 4 3 2

Sample Output

HINT

Source

[ ][ ][ ]

解题思路：因为题目要求每一次选择最左端数进行插入，直到序列为单调递增序列。因此，最优的策略为保持序列中到序列最右端单调序列的长度（至少为1，就是它本身），然后让不属于此单调序列的元素移动到合适的位置。

AC代码：

#include 
    
     #include
     
      #include
      
       #include
       
        using namespace std;int t,a[100005],sum,n;int main(){    scanf("%d",&t);    while(t--)    {        sum=1;        scanf("%d",&n);        for(int i=0;i
        
         =0;i--)        {            if(a[i]

转载地址：https://blog.csdn.net/ZP_nanfangguniang/article/details/52263151 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：csu1408

下一篇：FZU2230

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！