• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	
            
		
			


            

            隨筆 - 97, 文章 - 22, 評論 - 81, 引用 - 0
            

            


            		
	
            

            

            
	
            
		
			
            
				數(shù)據(jù)加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			ZJU 1440 Bone Sort
		
            
		
            
		
            題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1440
            

            /*
            題意：
                給定N(N <= 10000)個(gè)互不相等的數(shù)字ai，要求求出進(jìn)行至少多少
            次交換操作，使得數(shù)列遞增，并且輸出原數(shù)列的逆序?qū)Φ臄?shù)目。

            解法：
            樹狀數(shù)組

            思路：
                至少多少次交換可以采用貪心，每次找出數(shù)列中最小的那個(gè)數(shù)換到
            它應(yīng)該有的位置上，這一步可以采用hash，因?yàn)閿?shù)字都不相同并且有可
            能很大，事先離散化一下。求逆序數(shù)可以采用樹狀數(shù)組的區(qū)間求和，從
            后往前線性掃描，每次統(tǒng)計(jì)比當(dāng)前數(shù)小的sum和，然后將這個(gè)數(shù)插入到
            樹狀數(shù)組中，n次循環(huán)過后，累加的值就是逆序數(shù)了。
            */
            #include             <iostream>
            #include             <algorithm>
            #include             <cstdio>
            using namespace std;

            #define ll long long
            #define maxn 100010
            int c[maxn], val[maxn], bin[maxn], n;
            int pos[maxn];

            int Binary(int val) {
                            int l = 1;
                            int r = n;
                            while(l <= r) {
                                int m = (l + r) >> 1;
                                if(bin[m] == val)
                                    return m;
                                if(val > bin[m]) {
                        l             = m + 1;
                    }            else
                        r             = m - 1;
                }
            }

            int lowbit(int x) {
                            return x & (-x);
            }

            void add(int pos) {
                            while(pos <= n) {
                    c[pos]             ++;
                    pos             += lowbit(pos);
                }
            }
            int sum(int pos) {
                            int s = 0;
                            while(pos > 0) {
                    s             += c[pos];
                    pos             -= lowbit(pos);
                }
                            return s;
            }

            int main() {
                            int i;
                            while(scanf("%d", &n) != EOF) {
                                for(i = 1; i <= n; i++) {
                        scanf(            "%d", &val[i]);
                        bin[i]             = val[i];
                    }
                    sort(bin            +1, bin+1+n);
                                for(i = 1; i <= n; i++) {
                        val[i]             = Binary(val[i]);
                    }
                                for(i = 1; i <= n; i++)
                        c[i]             = 0;

                    ll ans             = 0;
                                int swp = 0;
                                for(i = n; i >= 1; i--) {
                        ans             += sum(val[i]-1);
                        add(val[i]);
                    }
                                for(i = 1; i <= n; i++) {
                        pos[ val[i] ]             = i;
                    }

                                for(i = 1; i <= n; i++) {
                                    if(val[i] != i) {    
                            swp             ++;
                            
                                        int pre = pos[i];
                                        int nowVal = val[i];
                            swap( val[ pre ], val[i] );

                            pos[ nowVal ]             = pre;
                        }
                    }
                    printf(            "%d\n%lld\n", swp, ans);
                }
                            return 0;
            }
            

		
            
		
            
			posted on 2011-04-06 11:38 英雄哪里出來 閱讀(1153) 評論(0)  編輯 收藏 引用  所屬分類: 樹狀數(shù)組 
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



国产成人精品久久综合|
久久久久久久国产免费看|
国产精品美女久久久久av爽|
久久婷婷午色综合夜啪|
亚洲午夜久久久久久久久久|
精品久久久久久久久久中文字幕
|
国产成年无码久久久久毛片|
一级做a爰片久久毛片16|
精品久久久无码21p发布|
精品久久国产一区二区三区香蕉|
久久精品麻豆日日躁夜夜躁|
三级片免费观看久久|
青青青国产成人久久111网站|
久久久久久久精品妇女99|
国产精品99久久久久久www|
久久综合国产乱子伦精品免费|
91精品国产91久久久久久|
午夜不卡久久精品无码免费|
久久精品成人免费网站|
久久亚洲精精品中文字幕|
欧美牲交A欧牲交aⅴ久久|
99久久国产精品免费一区二区|
亚洲欧洲久久久精品|
久久人人超碰精品CAOPOREN|
久久99精品久久久久久水蜜桃|
99久久国产综合精品成人影院|
国产—久久香蕉国产线看观看|
国产精品内射久久久久欢欢|
伊人丁香狠狠色综合久久|
久久精品国产半推半就|
久久精品国产精品亚洲精品|
91精品婷婷国产综合久久|
国内精品久久久久久久久电影网
|
欧美性大战久久久久久|
久久国产热这里只有精品|
久久国产精品无码HDAV|
色综合久久无码中文字幕|
国产精品欧美久久久久无广告|
人人狠狠综合久久亚洲|
777米奇久久最新地址|
亚洲欧美国产日韩综合久久|