TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7524
  • 题目
  • P7524[三校联测2] 排序
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    14 学完了排序,有感而发,又想出了一个比较妙的题目。

    14 有一个长度为 \(n\) 的序列 \(a\)里面的元素互不相同,14 要对它从小到大排序。

    14 每次可以选择两个不相同的位置 \(i,j\) ,交换这两个位置上的元素的代价为 \(a_i+a_j\)

    14 想知道将这个序列变成递增序列至少需要多少代价。

    输入格式

    输入第一行包含一个整数 \(n\),表示序列的长度。

    输入第二行包含 \(n\) 个整数,表示序列 \(a\)

    对于 $100 %$ 的数据, $1\le n\le 10^{6}$, $1\le a_i\le 10^9$。

    测试点编号 \(n\) 特殊限制
    $1\sim 2$ \(\le 10\) /
    $3\sim 6$ \(\ge 2\)\(\le 10^{6}\) 给出的序列满足一定有 \(n-1\) 个位置上的数为 \(a_i=i\)
    $7\sim 10$ \(\le 5\times 10^2\) /
    $11\sim 15$ \(\le 5\times 10^3\) /
    $16\sim 20$ / /
    输出格式

    输出只有一行,表示你的答案。

    样例输入 1

    4
    2 3 6 1

    样例输出 1

    14

    样例输入 2

    3
    2 3 1

    样例输出 2

    7

    提示

    样例2说明: 先交换 \(a_2\)\(a_3\),代价为 $1+3=4$,序列变为 2 1 3,再交换 \(a_1\)\(a_2\),代价为 $2+1=3$,序列变为 1 2 3

    所以总代价为 $7$,可以证明这是最小的代价。