• <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ù)組 
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



国产成人久久精品一区二区三区|
亚洲精品无码久久久久去q|
精品蜜臀久久久久99网站|
亚洲精品乱码久久久久久蜜桃图片
|
日本加勒比久久精品|
久久精品国产99国产精品导航|
色欲综合久久中文字幕网|
四虎国产精品免费久久5151|
亚洲精品成人久久久|
久久精品国产免费观看三人同眠|
91精品国产综合久久精品|
久久精品无码一区二区三区免费
|
亚洲综合日韩久久成人AV|
韩国三级大全久久网站|
国产99久久久国产精品小说|
国产V亚洲V天堂无码久久久|
久久亚洲国产成人精品无码区|
久久久久女人精品毛片|
国产精品久久久久久久人人看
|
精品九九久久国内精品|
国产精品久久久久免费a∨|
国产精品伊人久久伊人电影
|
精品国产青草久久久久福利|
久久99精品国产麻豆|
99久久这里只精品国产免费|
国产99久久久久久免费看|
久久99热只有频精品8|
亚洲中文字幕无码久久综合网
|
99re久久精品国产首页2020|
人妻无码精品久久亚瑟影视
|
久久久久亚洲AV成人网|
国产精品久久久久久|
久久夜色精品国产噜噜亚洲AV|
要久久爱在线免费观看|
日韩电影久久久被窝网|
久久久久99精品成人片牛牛影视|
久久99国产精品二区不卡|
2021精品国产综合久久|
久久久久久免费一区二区三区|
久久精品国产免费一区|
中文精品久久久久国产网址|