魔法学徒排队
成绩 | 100 | 开启时间 | 2019年08月30日 星期五 18:15 |
折扣 | 0.8 | 折扣时间 | 2019年08月30日 星期五 18:15 |
允许迟交 | 是 | 关闭时间 | 2019年08月30日 星期五 18:15 |
输入文件 | HappySort.in | 输出文件 | HappySort.out |
【题目描述】魔法学徒排队(HappySort)2014 蓝桥杯
n 个魔法学徒站成一排。现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个学徒。
每个学徒都有一个不高兴的程度。初始时所有学徒的不高兴程度都是0。
如果某个学徒第一次被要求交换,则他的不高兴程度增加1,如果第二次要求他交换,则他的不高兴程度增加2(即不高兴程度为3),依次类推。当要求某个学徒第k次交换时,他的不高兴程度增加k。
试求让所有学徒按从低到高排队,他们的不高兴程度之和最小是多少。
如果有两个学徒身高一样,则他们谁站在谁前面是没有关系的。
【输入格式】
输入的第一行包含一个整数n,表示学徒的个数。
第二行包含 n 个整数 H1,H2,… ,Hn,分别表示每个学徒的身高。
【输出格式】
输出一行,包含一个整数,表示学徒的不高兴程度和的最小值。
【输入样例】
3
3 2 1
【输出样例】
9
【样例说明】
首先交换身高为3和2的学徒,再交换身高为3和1的学徒,再交换身高为2和1的学徒,每个学徒的不高兴程度都是3,总和为9。
【数据规模】
对于100%的数据,1≤n≤100 000,0≤Hi≤1 000 000。