企业官网建设流程全解析

P8613 [蓝桥杯 2014 省 B] 小朋友排队

题目描述

nnn个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是000。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加111，如果第二次要求他交换，则他的不高兴程度增加222（即不高兴程度为333），依次类推。当要求某个小朋友第kkk次交换时，他的不高兴程度增加kkk。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入格式

输入的第一行包含一个整数nnn，表示小朋友的个数。

第二行包含nnn个整数H1,H2⋯HnH_1,H_2 \cdots H_nH1​,H2​⋯Hn​，分别表示每个小朋友的身高。

输出格式

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

输入输出样例 #1

输入 #1

3 3 2 1

输出 #1

9

说明/提示

【样例说明】

首先交换身高为333和222的小朋友，再交换身高为333和111的小朋友，再交换身高为222和111的小朋友，每个小朋友的不高兴程度都是333，总和为999。

【数据规模与约定】

对于10%10\%10%的数据，1≤n≤101 \le n \le 101≤n≤10；

对于30%30\%30%的数据，1≤n≤10001 \le n \le 10001≤n≤1000；

对于50%50\%50%的数据，1≤n≤100001 \le n \le 100001≤n≤10000；

对于100%100\%100%的数据，1≤n≤1000001 \le n \le 1000001≤n≤100000，0≤Hi≤10000000 \le H_i \le 10000000≤Hi​≤1000000。

时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛

C++实现

#include<bits/stdc++.h>usingnamespacestd;longlongn,a[500005],b[500005],t[500005],cnt[500005],ans;map<longlong,int>m;longlonglowbit(longlongx){returnx&(-x);}longlonggetsum(longlongx){longlongsum=0;while(x){sum+=t[x];x-=lowbit(x);}returnsum;}voidupdate(longlongx,longlongy){while(x<=500000){t[x]+=y;x+=lowbit(x);}}intmain(){scanf("%lld",&n);for(inti=1;i<=n;i++){scanf("%lld",&a[i]);b[i]=a[i];}sort(b+1,b+n+1);for(inti=1;i<=n;i++){m[b[i]]=i;}for(inti=1;i<=n;i++){a[i]=m[a[i]];}for(inti=1;i<=n;i++){update(a[i],1);//数字可以是0，所以要加1cnt[i]+=(i-getsum(a[i]));//统计前面比它大的数字}memset(t,0,sizeof(t));for(inti=n;i>=1;i--){update(a[i],1);cnt[i]+=getsum(a[i]-1);//统计后面比它小的数字}for(inti=1;i<=n;i++){ans+=(cnt[i]+1)*cnt[i]/2;//算出这个数字的代价}printf("%lld",ans);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容