程序地带

蓝桥杯-小朋友排队


蓝桥杯-小朋友排队

问题描述   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。 数据规模和约定   对于10%的数据, 1<=n<=10;   对于30%的数据, 1<=n<=1000;   对于50%的数据, 1<=n<=10000;   对于100%的数据,1<=n<=100000,0<=Hi<=1000000。


对于这样一个问题,可能最先想到的就是冒泡排序直接模拟解决,但是从数据规模和约定中可以看出10w人的数量显然不是算法复杂度为O(n^2)的冒泡排序所能驾驭的。因此思路转换到是否可以找出时间复杂度更优的算法来解决这个问题。   其实这是一个逆序对问题,解决这类问题的一个好方法便是使用树状数组维护逆序对。此题中还可以给每个小朋友加一个初始下标,以标记他们的相对位置,这用到了坐标离散化的思想,这样在小朋友们按照身高排序后更新树状数组时仍然可以用小朋友的初始位置(即离散化添加的下标)来计算该位置的逆序对个数。


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct child{
int h,index;
};
const int maxn=100010;
long long n,ans,tree[maxn],num[maxn];
child c[maxn];
bool cmp(child a,child b){
if(a.h==b.h){
return a.index<b.index;
}
return a.h<b.h;
}
int lowbit(int x){
return x&(-x);
}
void updata(int i){
while(i<=n){
tree[i]++;
i+=lowbit(i);
}
}
long long getsum(int i){
int sum=0;
while(i>0){
sum+=tree[i];
i-=lowbit(i);
}
return sum;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i].h;
c[i].index=i;
}
sort(c+1,c+1+n,cmp);
//计算左边比自己大的
//循环正向左边的先记录进入树状数组 此时getsum查询到的是前面比x位置小于等于的数量
//i表示已经更新的个数 getsum取得的是左侧小于等于idx位置的值
for(int i=1;i<=n;i++){
updata(c[i].index);
num[i]+=(i-getsum(c[i].index));
}
memset(tree,0,sizeof(tree));
//计算右边比自己小的
//循环反向后右边的先记录进入树状数组 此时getsum查询到的是后面比x位置小于等于的数
for(int i=n;i>=1;i--){
updata(c[i].index);
num[i]+=getsum(c[i].index-1);
}
for(int i=1;i<=n;i++){
ans+=(((num[i]+1)*num[i])/2); //该公式表示从1加到n的和
}
cout<<ans;
return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45939365/article/details/109757219

随机推荐

Markdown 转 PDF

参考:最完善的markdown转html/pdf方法、带目录生成目录MarkdownPreviewEnhanced安装预览Markdown生成目录输出HTML/PDFMarkdownPr...

连理o 阅读(959)

ORACLE_OCP多租户之CDB与PDB的安全管理

ORACLE_OCP多租户之CDB与PDB的安全管理文章目标管理公共用户和本地用户管理公共和本地角色管理公共和本地权限管理公共用户的CONTAINER_DATA属性管理公共和本地概要文件一、用户&#x...

XiaoHG_CSDN 阅读(193)

数据仓库主题域如何划分

1.关于主题:   数据仓库中的数据是面向主题组织的,主题是在较高层次上将企业信息系统中的数据进行综合、归类和分析利用的一个抽象概念,每一个主题基本对应一个宏...

吃鱼的羊 阅读(669)

JDK1.8学习(七)TreeSet源码

文章目录一、TreeSet概述1.1TreeSet继承关系1.2TreeSet特点二、TreeSet源码2.1构造方法2.2添加元素2.3删除元素2.4查找元素2.5获取TreeSet元素个数2.6判...

解梦者 阅读(666)

02:输出绝对值

总时间限制:1000ms内存限制:65536kB描述输入一个浮点数,输出这个浮点数的绝对值。输入输入一个浮点数,其绝对值不超过10000。输出输出这个浮点数的绝对值...

卜凡. 阅读(831)

python随时导入自定义模块

Python_模块与包的使用如何随时导入自定义模块如何找到Python包的系统安装目录如何随时导入自定义模块把我们编辑好的模块文件(.py)放到安装目录下lib/site-...

刀客熊 阅读(700)