A25981. 最佳策略
填空题
较易
知识点
题目描述
最佳策略
题目描述
有n个小朋友排成一排，现在需要按身高从低到高的顺序进行排列。排序方式为：如果位置相邻的两个小朋友不符合从低到高的顺序，就交换这两个小朋友的位置。且每个小朋友都有一个不高兴的数值，开始的时候，所有小朋友的不高兴值为0。如果某个小朋友第一次被交换，则他的不高兴值加1,如果第二次被交换，则他的不高兴值加2,如果第三次被交换，则他的不高兴值加3,依此类推。
假如：一个小朋友被交换了3次，他的不高兴值为6(1+2+3)。
如果让所有小朋友都按从低到高的顺序排好队，那么所有小朋友的不高兴值的总和的最小值是多少(也就是交换次数最少，不高兴值得总和最小)。
注意：
1.如果有两个小朋友身高一样，谁在谁前无所谓(不需要交换);
2.每次交换的两个小朋友都需要增加不高兴值。
输入描述
第一行输入一个正整数n(2<n<51)表示小朋友的数量。
第二行输入n个正整数(每个正整数<160),分别表示n个小朋友的身高，正整数之间以一个空格隔开。
输出描述
输出所有小朋友的不高兴值的总和的最小值。
样例输入
3
130 115 98样例输出
9参考答案
#include <cstdio>
#include <cstring>
#include <iostream>
#define maxn 100005
#define MAXN 1000005
using namespace std;
int c[MAXN], a[MAXN];
long long b[maxn];
int n;
// 获取最小比特
int lowbit(int x)
{
return x & (-x);
}
// 获取前x项和
int getSum(int x) {
int s = 0;
for (int i = x; i; i -= lowbit(i))
s += c[i];
return s;
}
// 修改更新
void add(int x, int val)
{
for (int i = x; i < MAXN; i += lowbit(i)) {
c[i] += val;
}
}
int main() {
scanf("%d", &n);
// 左边逆序对
memset(c, 0, sizeof(c));
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
add(a[i] + 1, 1);
b[i] = (i + 1) - getSum(a[i] + 1);
}
// 右边逆序对
memset(c, 0, sizeof(c));
for (int i = n - 1; i >= 0; i--) {
add(a[i] + 1, 1);
b[i] += getSum(a[i]);
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += (1 + b[i]) * b[i] / 2;
}
printf("%lld\n", ans);
}
上一题
下一题