HDU2838Cow Sorting（树状数组）-白红宇

HDU2838Cow Sorting（树状数组）

阅读量：5024 次

发布时间：2019-06-12

本文共 1846 字，大约阅读时间需要 6 分钟。

题目意思是说给你一列数，每次可以将相邻的两个数交换，这一步的代价是这两个数的和，求将所有数排好序的最少代价。

题解：

我们可以这么思考，由于每次都是交换相邻的两个数，所以将一个数放到它自己的位置去后，其他的数的相对位置没变，那么排序其他的数所需要消耗的代价将与这个数没关系，所以排序过程将相当于是冒泡排序。

这样的话我们用树状数组可以记录第i个数之前有多少个比它小的的数x

再记录这些比它小的数的和是多少sum

然后这个数移动到他自己的位置的代价就是

　　x*a[i]+sum。

最后的复杂度就是nlogn

以后排序和求和的题应该多想想树状数组~恩恩

1 #include  2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 using namespace std;15 #define INF 0x3f3f3f3f16 #define MAX(a,b) (a > b ? a : b)17 #define MIN(a,b) (a < b ? a : b)18 #define mem0(a) memset(a,0,sizeof(a))19 #define mem1(a) memset(a,-1,sizeof(a))20 #define lson k<<1, L, mid21 #define rson k<<1|1, mid+1, R22 23 typedef long long LL;24 const double eps = 1e-12;25 const int MAXN = 100005;26 const int MAXM = 500005;27 28 29 struct NODE30 {31 int num;//记录个数32 __int64 sum;//记录比它小的数的和33 }c[MAXN];34 int N;35 36 void init()37 {38 mem0(c);39 }40 41 int lowbit(int x)42 {43 return x & (-x);44 }45 46 void edit(int k, int num)47 {48 while(k <= 100000)49 {50 c[k].num += 1;51 c[k].sum += num;52 k += lowbit(k);53 }54 }55 56 int getnum(int k)//得到比当前数小的数的个数57 {58 int num = 0;59 while(k > 0)60 {61 num += c[k].num;62 k -= lowbit(k);63 }64 return num;65 }66 67 __int64 getsum(int k)//得到比当前数小的数的和68 {69 __int64 sum = 0;70 while(k>0)71 {72 sum += c[k].sum;73 k-=lowbit(k);74 }75 return sum;76 }77 78 int main()79 {80 while(~scanf("%d", &N))81 {82 init();83 int num;84 __int64 ans = 0;85 for(int i=1;i<=N;i++)86 {87 scanf("%d", &num);88 edit(num, num);89 int cnt = i - getnum(num);//有cnt的数比num大90 if(cnt != 0)91 {92 ans += (__int64)cnt*num + getsum(100000)-getsum(num);93 }94 }95 printf("%I64d\n", ans);96 }97 return 0;98 }

转载于:https://www.cnblogs.com/gj-Acit/p/3452022.html

你可能感兴趣的文章