19ty53 2020-02-04 11:32
浏览 454

----- ——————插入排序——————--------

题目描述
有依次排列的一列数a1,a2,a3,…,an-1,an。你可以随便把一个数拿出,插到最前面(当前第1个数a1前)、最后面(当前最后一个数an后面)、或者剩余数列中任意的相邻两个数之间。
比如起始数依次为4 5 6 7 8 9。如果把第4个数a4=7拿出,然后任意放回,可能有
7 4 5 6 8 9
4 7 5 6 8 9
4 5 7 6 8 9
4 5 6 7 8 9
4 5 6 8 7 9
4 5 6 8 9 7
这6种排列。
已知把第i个数ai拿出后插回去花费的代价为该数的值ai。小猪希望花费最少的代价来把这个数列排成不降序列。所谓不降序列,是指对于数列中任意两个数,排在前面的数小于等于排在后面的数。
输入
输入文件insert.in的第一行只有一个整数n,表示共有n个整数。
第2行有n个整数(互相之间以一个空格分隔),表示待排序的n个数。
输出
输出文件insert.out中只有一行,该行只有一个整数,表示花费的最小代价。
样例输入 Copy
4
7 1 2 3
样例输出 Copy
6
提示
【样例说明】
很显然移动7是不划算的。一种移动方法是:
初始情况:7 1 2 3 => (把3移到最前面得) 3 7 1 2
=> (把1移到最前面得) 1 3 7 2
=> (把2移到1与3之间得) 1 2 3 7 最终整个序列成为升序。
消耗的代价是3 + 1 + 2 = 6。
【数据规模】
30%的数据初始数列是1至n的一个排列,即1至n都在初始数列出现且仅出现一次;
20%的数据,1≤n≤10;
90%的数据,1≤n≤1000;
100%的数据,1≤n≤100000,初始数列的每个数在1和20000之间(包括1和20000)。
【提示】
不需要移动的数之间符合什么规律呢?

  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 请提交代码 7月18日

    悬赏问题

    • ¥15 lammps Gpu加速出错
    • ¥15 关于PLUS模型中kapaa值的问题
    • ¥15 关于博途V17进行仿真时无法建立连接问题
    • ¥15 机器学习教材中的例题询问
    • ¥15 求.net core 几款免费的pdf编辑器
    • ¥15 为什么安装HCL 和virtualbox之后没有找到VirtualBoxHost-OnlyNetWork?
    • ¥15 C# P/Invoke的效率问题
    • ¥20 thinkphp适配人大金仓问题
    • ¥20 Oracle替换.dbf文件后无法连接,如何解决?(相关搜索:数据库|死循环)
    • ¥15 数据库数据成问号了,前台查询正常,数据库查询是?号