英雄哪里出來

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

數據加載中……

ZJU 1440 Bone Sort

題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1440

題意：

給定N(N <= 10000)個互不相等的數字ai，要求求出進行至少多少

次交換操作，使得數列遞增，并且輸出原數列的逆序對的數目。

解法：

樹狀數組

思路：

至少多少次交換可以采用貪心，每次找出數列中最小的那個數換到

它應該有的位置上，這一步可以采用hash，因為數字都不相同并且有可

能很大，事先離散化一下。求逆序數可以采用樹狀數組的區間求和，從

后往前線性掃描，每次統計比當前數小的sum和，然后將這個數插入到

樹狀數組中，n次循環過后，累加的值就是逆序數了。

#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) 編輯收藏引用所屬分類: 樹狀數組

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: HDU 2688 Rotate PKU 3145 Harmony Forever PKU 1990 MooFest PKU 2828 Buy Tickets PKU 3067 Japan HDU 2871 Memory Control HDU 1166 敵兵布陣 ZJU 1484 Minimum Inversion Number PKU 3378 Crazy Thairs PKU 2892 Tunnel Warfare

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

英雄哪里出來

ZJU 1440 Bone Sort

導航

常用鏈接

留言簿(22)

隨筆分類(102)

文章分類(22)

ACM

搜索

積分與排名

最新評論