网域高科学校网站管理系统,企业融资以什么为基础,建设部网站监理工程师查询,北京网站定制价格表n n n 个小朋友站成一排。
现在要把他们按身高从低到高的顺序排列#xff0c;但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。
开始的时候#xff0c;所有小朋友的不高兴程度都是 0 0 0。
如果某个小朋友第一次被要求交换#xff0c;则他的不… n n n 个小朋友站成一排。
现在要把他们按身高从低到高的顺序排列但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。
开始的时候所有小朋友的不高兴程度都是 0 0 0。
如果某个小朋友第一次被要求交换则他的不高兴程度增加 1 1 1如果第二次要求他交换则他的不高兴程度增加 2 2 2即不高兴程度为 3 3 3依次类推。当要求某个小朋友第 k k k 次交换时他的不高兴程度增加 k k k。
请问要让所有小朋友按从低到高排队他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样则他们谁站在谁前面是没有关系的。
输入格式 输入的第一行包含一个整数 n n n表示小朋友的个数。
第二行包含 n n n 个整数 H 1 , H 2 , … , H n H_1,H_2,…,H_n H1,H2,…,Hn分别表示每个小朋友的身高。
输出格式 输出一行包含一个整数表示小朋友的不高兴程度和的最小值。
数据范围 1 ≤ n ≤ 100000 , 1≤n≤100000, 1≤n≤100000, 0 ≤ H i ≤ 1000000 0≤H_i≤1000000 0≤Hi≤1000000 输入样例
3
3 2 1输出样例
9样例解释 首先交换身高为 3 3 3 和 2 2 2 的小朋友再交换身高为 3 3 3 和 1 1 1 的小朋友再交换身高为 2 2 2 和 1 1 1 的小朋友每个小朋友的不高兴程度都是 3 3 3总和为 9 9 9 。 首先明确只能相邻的人之间换而且每次换的时候比如 1 1 1 和 2 2 2 换那么他们两个人的不高兴都会加上他们各自交换过的次数。
对于样例我们只看中间的 22 的左边有一个 3这个 3 应该在 2 的右边2 的右边有一个 1这个 1 应该在 2 的左边不管怎么换 2 都会被换两次因为如果 2 先和 3 换3 和 1 换1 和 2 换 2 换了两次如果 2 先和 1 换 3 和 1 换3 和 2 换2 还是换了两次。
对于 1 也是因为左边有两个比他大的所以 1 要换两次。
对于任何一个数如果左边有比他大的就一定要跨过他去如果右边有比他小的也一定要跨过他去这么下来就交换了左边比他大的个数加右边比他小的个数的次数这样得来的就已经是最小的交换次数了因为不可能比这个小的情况如果有就不满足升序了。
那么我们就需要实现求出来某个数左边比他大的数的个数和右边比他小的数的个数。可以有很多方法这里使用树状数组实现。
这里树状数组代表的是某个数有没有如果有就是 1没有就是 0 。 之后如果要求a[i]的左边比它大的数只要求从左边扫过去然后求出最大高度的前缀和减去a[i]的前缀和 求右边的比当前数小的数则是从右边扫其他的同理。
此种做法是树状数组的一种管用用法可以参考树状数组的笔记
代码
#includeiostream
#includecstring
using namespace std;
const int N 1e5 10;
const int M 1e6 10;int tr[M];
int a[N];
int n;
int times[N]; //存每个数的交换个数int lowbit(int x) { return x -x; }
void add(int x, int c) {for (int i x; i M; ilowbit(i))tr[i] c;
}
int sum(int x) {int res 0;for (int i x; i; i - lowbit(i))res tr[i];return res;
}int main() {cin n;for (int i 1; i n; i) {cin a[i];a[i] ;}for (int i 1; i n; i) {times[i] sum(M) - sum(a[i]);add(a[i], 1);}memset(tr, 0, sizeof tr);for (int i n; i 1; i--) {times[i] sum(a[i] - 1);add(a[i], 1);}long long res 0;for (int i 1; i n; i) {res (long long)(1 times[i]) * times[i] / 2; //注意根据题目条件答案要求等差数列的和}cout res;return 0;
}
