欧美日韩亚洲成人,亚洲免费在线视频,欧美日韩中文字幕综合视频

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)過(guò)后，累加的值就是逆序數(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 英雄哪里出來(lái) 閱讀(1164) 評(píng)論(0) 編輯收藏引用所屬分類: 樹狀數(shù)組

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

英雄哪里出來(lái)

ZJU 1440 Bone Sort

導(dǎo)航

常用鏈接

留言簿(22)

隨筆分類(102)

文章分類(22)

ACM

搜索

積分與排名

最新評(píng)論