高端网站设计 必荐骏网添城科技,台州椒江网站制作公司,十大房产中介软件,佛山设计网站公司吗小朋友排队 n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列#xff0c;但是每次只能交换位置相邻的两个小朋友。 每个小朋友都有一个不高兴的程度。开始的时候#xff0c;所有小朋友的不高兴程度都是0。 如果某个小朋友第一次被要求交换#xff0c;则他的不高兴…小朋友排队 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%的数据 1n10 对于30%的数据 1n1000 对于50%的数据 1n10000 对于100%的数据1n1000000Hi1000000。 资源约定 峰值内存消耗 256M CPU消耗 1000ms 请严格按要求输出不要画蛇添足地打印类似“请您输入...” 的多余内容。 所有代码放在同一个源文件中调试通过后拷贝提交该源码。 注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C 标准不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include 不能通过工程设置而省略常用头文件。 提交时注意选择所期望的编译器类型。 思路一求逆序对左边大于它的 右边小于它的数量求完逆序对后,计算等差数列和 (因为不高兴程度每次增加k) 待改进只能过50%的数据超时了。需要用归并排序 和 树状数组改进。 #includeiostream
using namespace std;int n;
int arr[1000010];
long long ans 0;/*
求逆序对左边大于它的 右边小于它的数量
求完逆序对后,计算等差数列和 (因为不高兴程度每次增加k)
*/ long long cal(long long x){return x x*(x-1)/2;
}int main(){cinn;for(int i1;in;i){cinarr[i];}for(int i1;in;i){long long ans1 0;long long ans2 0;for(int j1;ji;j){if(arr[j] arr[i]){ans1;}}for(int ji1;jn;j){if(arr[j]arr[i]){ans2;}}anscal(ans1 ans2); }coutansendl;
} 思路二使用树状数组优化求逆序对 先熟悉树状数组原理及其应用。 1.这道题可以转换成求每个位置的左边比他小的个数和右边比他大的个数这两个相加就是这个人要被交换的次数然后根据等差数列前n项求和公式(a1an)*n/2将所有位置和相加即可。 2.求逆序数用树状数组优化成 nlogm,树状数组是专门用来求前缀和的这里从位置0遍历到n-1把高度作为树状数组的下标每个高度对应的个数作为树状数组的值对于输入的小朋友高度a[i]在当前小朋友左边比当前小朋友a[i]高的总数就是树状数组s(maxh)-s(a[i])i1-s(a[i])反之同理。 注意事项: 1.题中a[i]可以等于0所以要把输入加一不然在后面计算sum(a[i]-1)处会越界。 2.代码中a数组是保存输入,d数组的下标是高度lr数组是保存位置i的左右逆序总数,maxh是输入的最大值 代码 #include iostream
#include cstdio
#define _for(i,a,b) for(int ia;ib;i)
#define _unfor(i,a,b) for(int ia;ib;i--)
#define mset(a,val,n) for(int i0;in;i)a[i]val;
#define lowbit(x) (x(-x))
using namespace std;
typedef long long LL;int a[100005],d[1000005],n,lr[100005],maxh0;
//tree_arrvoid add(int i,int x){while(imaxh1)d[i]x,ilowbit(i);}int sum(int i){int res0;while(i0)resd[i],i-lowbit(i);return res;}
//
int main(){scanf(%d,n);_for(i,0,n){scanf(%d,a[i]);maxhmax(maxh,a[i]);}_for(i,0,n){add(a[i],1);lr[i]i1-sum(a[i]);}mset(d,0,maxh5);_unfor(i,n-1,0){add(a[i],1);lr[i]sum(a[i]-1);}LL ans0;_for(i,0,n){LL klr[i];ansk*(k1)/2;}coutansendl;
} 转载于:https://www.cnblogs.com/fisherss/p/10286608.html
