学生排队
成绩 | 100 | 开启时间 | 2020年02月20日 星期四 20:45 |
折扣 | 0.8 | 折扣时间 | 2020年02月20日 星期四 20:45 |
允许迟交 | 是 | 关闭时间 | 2020年02月20日 星期四 20:45 |
输入文件 | HappySort.in | 输出文件 | HappySort.out |
【题目描述】学生排队(HappySort)2014 蓝桥杯
n 个学生站成一排,每个学生都有一个不高兴的程度,初始时所有学生的不高兴程度都是0。
现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个学生。
当要求某个学生第k次交换时,他的不高兴程度增加k。例如某个学生第一次被要求交换,则他的不高兴程度增加1,如果第二次要求他交换,则他的不高兴程度增加2(即不高兴程度为3),依次类推。
试求让所有学生按从低到高排队,他们的不高兴程度之和最小是多少。
如果有两个学生身高一样,则他们谁站在谁前面是没有关系的。
【输入格式】
输入的第一行包含一个整数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。