[STEMA 2021 中级组] 最佳策略
时间限制:1 S
内存限制:64 MB
【题目描述】
有 \(n\) 个小朋友排成一排,现在需要按身高从低到高的顺序进行排列。排列方式为:如果位置相邻的两个小朋友不符合从低到高的顺序,就交换这两个小朋友的位置。且每个小朋友都有一个不高兴的数值,开始的时候,所有小朋友不高兴值为 \(0\) 。如果某个小朋友第一次被交换,则他的不高兴值加 \(1\) ,如果第二次被交换,则他的不高兴值加 \(2\) ,如果第三次被交换,则他的不高兴值加 \(3\) ,依此类推。
假如:
一个小朋友被交换了 \(3\) 次,他的不高兴值为 \(6\) (\(1 + 2 + 3\)) 。
如果让所有小朋友都按从低到高的顺序排好队,那么所有小朋友的不高兴值之和的最小值是多少(找到最优的交换方式,也就是总的交换次数最少,这样不高兴值之和最小)。
注意:
如果有两个小朋友身高一样,谁在谁前无所谓(不需要交换);
每次交换的两个小朋友都需要增加不高兴值。
【输入格式】
输入共两行,第一行输入一个正整数 \(n\) (\(2 \lt n \lt 50\)) 表示小朋友的数量。
第二行输入 \(n\) 个正整数(每个正整数 \(\lt 160\)),分别表示 \(n\) 个小朋友的身高,正整数之间以一个空格隔开。
【输出格式】
输出所有小朋友的不高兴值之和的最小值。
样例 1
【样例 1 输入】
3
130 115 98
【样例 1 输出】
9
【样例 1 解释】
首先交换身高为 \(130\) 和 \(115\) 的小朋友,再交换身高为 \(130\) 和 \(98\) 的小朋友,再交换身高为 \(115\) 和 \(98\) 的小朋友,每个小朋友都交换了两次,两次的不高兴值之和为 \(1\) 和 \(2\) ,和为 \(3\) 。所以三个小朋友的不高兴值之和为 \(9\) 。
信息
- ID
- 1006
- 难度
- 1
- 分类
- (无)
- 标签
- 递交数
- 6
- 已通过
- 2
- 通过率
- 33%
- 上传者