本文共 2554 字,大约阅读时间需要 8 分钟。
3231
7 Hint Input DetailsThree cows are standing in line with respective grumpiness levels 2, 3, and 1.Output Details2 3 1 : Initial order.2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4).1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3).
题意:你可以将相邻的数相互交换最终使得数组有序。(代价是每次花费相邻数和的时间)
思路:运用冒泡排序的思想,对于当前数x而言,x会交换k次(设k为前面大于x的数的个数),设为前面大于x的数的和为sum,所以time = k*x + sum。
前面大于x的数的个数也就是逆序,用树状数组求解。
/*hdu2838树状数组nlogn求逆序数*/#include#include #include using namespace std;typedef long long ll;const int N = 100005;struct node{ int num; ll sum;}C[N];int n;int lowbit(int t){ return t&(-t);}void add(int t,int k,int s){ while(t <= n) { C[t].num += k; C[t].sum += s; t += lowbit(t); }}//求得前面小于当前的数的个数int getnum(int t){ int ans = 0; while(t > 0) { ans += C[t].num; t -= lowbit(t); } return ans;}//前面所有小于当前数的和ll getsum(int t){ ll ans = 0; while(t > 0) { ans += C[t].sum; t -= lowbit(t); } return ans;}int main(){ while(~scanf("%d",&n)) { memset(C,0,sizeof(C)); int x; ll ans = 0; for(int i = 1;i <= n;i++) { scanf("%d",&x); add(x,1,x); ll k = i - getnum(x);//逆序数 if(k != 0) { ans += k*x + getsum(n) - getsum(x); } } printf("%lld\n",ans); } return 0;}
转载地址:http://gmzgf.baihongyu.com/