• <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)個互不相等的數(shù)字ai，要求求出進(jìn)行至少多少
            次交換操作，使得數(shù)列遞增，并且輸出原數(shù)列的逆序?qū)Φ臄?shù)目。

            解法：
            樹狀數(shù)組

            思路：
                至少多少次交換可以采用貪心，每次找出數(shù)列中最小的那個數(shù)換到
            它應(yīng)該有的位置上，這一步可以采用hash，因?yàn)閿?shù)字都不相同并且有可
            能很大，事先離散化一下。求逆序數(shù)可以采用樹狀數(shù)組的區(qū)間求和，從
            后往前線性掃描，每次統(tǒng)計比當(dāng)前數(shù)小的sum和，然后將這個數(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 英雄哪里出來 閱讀(1158) 評論(0)  編輯 收藏 引用  所屬分類: 樹狀數(shù)組 
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



69久久精品无码一区二区|
国产一区二区三区久久|
精品99久久aaa一级毛片|
久久99国产精品久久99|
色综合久久久久综合99|
少妇高潮惨叫久久久久久|
亚洲国产精品久久66|
亚洲一区精品伊人久久伊人|
欧美牲交A欧牲交aⅴ久久
|
久久人人爽人人人人爽AV
|
久久99精品久久久久久|
国产精品永久久久久久久久久|
亚洲国产小视频精品久久久三级|
久久婷婷成人综合色综合|
99久久人人爽亚洲精品美女|
99久久精品国产一区二区|
久久99精品久久久久久齐齐|
久久无码人妻一区二区三区
|
久久精品国产99久久丝袜|
久久精品水蜜桃av综合天堂|
久久久久久A亚洲欧洲AV冫|
久久久久人妻一区二区三区vr|
久久久久亚洲AV无码去区首|
精品久久久久久亚洲精品|
人妻无码αv中文字幕久久琪琪布|
久久精品成人国产午夜|
久久精品中文闷骚内射|
一本久久a久久精品vr综合|
日韩美女18网站久久精品
|
无码国内精品久久人妻蜜桃|
久久久久一本毛久久久|
欧美久久精品一级c片片|
77777亚洲午夜久久多喷|
99久久人妻无码精品系列|
久久丫忘忧草产品|
久久婷婷色综合一区二区|
久久久久国产精品麻豆AR影院
|
99久久99这里只有免费费精品|
99精品久久久久久久婷婷|
久久久久亚洲AV无码观看|
一本色道久久88—综合亚洲精品|