P8613 [蓝桥杯 2014 省 B] 小朋友排队题目描述nnn个小朋友站成一排。现在要把他们按身高从低到高的顺序排列但是每次只能交换位置相邻的两个小朋友。每个小朋友都有一个不高兴的程度。开始的时候所有小朋友的不高兴程度都是000。如果某个小朋友第一次被要求交换则他的不高兴程度增加111如果第二次要求他交换则他的不高兴程度增加222即不高兴程度为333依次类推。当要求某个小朋友第kkk次交换时他的不高兴程度增加kkk。请问要让所有小朋友按从低到高排队他们的不高兴程度之和最小是多少。如果有两个小朋友身高一样则他们谁站在谁前面是没有关系的。输入格式输入的第一行包含一个整数nnn表示小朋友的个数。第二行包含nnn个整数H1,H2⋯HnH_1,H_2 \cdots H_nH1​,H2​⋯Hn​分别表示每个小朋友的身高。输出格式输出一行包含一个整数表示小朋友的不高兴程度和的最小值。输入输出样例 #1输入 #13 3 2 1输出 #19说明/提示【样例说明】首先交换身高为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≤1000000≤Hi≤10000000 \le H_i \le 10000000≤Hi​≤1000000。时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛C实现#includebits/stdc.husingnamespacestd;longlongn,a[500005],b[500005],t[500005],cnt[500005],ans;maplonglong,intm;longlonglowbit(longlongx){returnx(-x);}longlonggetsum(longlongx){longlongsum0;while(x){sumt[x];x-lowbit(x);}returnsum;}voidupdate(longlongx,longlongy){while(x500000){t[x]y;xlowbit(x);}}intmain(){scanf(%lld,n);for(inti1;in;i){scanf(%lld,a[i]);b[i]a[i];}sort(b1,bn1);for(inti1;in;i){m[b[i]]i;}for(inti1;in;i){a[i]m[a[i]];}for(inti1;in;i){update(a[i],1);//数字可以是0所以要加1cnt[i](i-getsum(a[i]));//统计前面比它大的数字}memset(t,0,sizeof(t));for(intin;i1;i--){update(a[i],1);cnt[i]getsum(a[i]-1);//统计后面比它小的数字}for(inti1;in;i){ans(cnt[i]1)*cnt[i]/2;//算出这个数字的代价}printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容