程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1394 Minimum Inversion Number 樹狀數組&amp;&amp;線段樹

HDU 1394 Minimum Inversion Number 樹狀數組&amp;&amp;線段樹

編輯：C++入門知識

題目給了你一串序列，然後每次把最後一個數提到最前面來，直到原來的第一個數到了最後一個，每次操作都會產生一個新的序列，這個序列具有一個逆序數的值，問最小的你逆序數的值為多少

逆序數麼最好想到的是樹狀數組，敲了一把很快，注意把握把最後一個數提上來對逆序數的影響即可，

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const LL INF = 1LL<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

int n;

int c[10000 + 5];

int num[10000 + 5];

void init() {
	memset(c,0,sizeof(c));
	memset(num,0,sizeof(num));
}

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

void add(int i,int val) {
	while(i <= n) {
		c[i] += val;
		i += lowbit(i);
	}
}

int get_sum(int i) {
	int sum = 0;
	while(i > 0) {
		sum += c[i];
		i -= lowbit(i);
	}
	return sum;
}

int main() {
	while(scanf("%d",&n) == 1) {
		init();
		
		int ans = 0;
		for(int i=1;i<=n;i++) {
			scanf("%d",&num[i]);
			num[i]++;
			add(num[i],1);
			ans += (i - get_sum(num[i]));
		}
		int minn = ans;
		for(int i=n;i>1;i--) {
			ans = ans + num[i] + num[i] - n - 1;
			minn = min(ans,minn);
		}
		printf("%d\n",minn);
	}
	return 0;
}

線段樹：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const LL INF = 1LL<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;


const int N = 10000 + 5;

int num[N];


typedef struct Node {
    int a;
    int l,r;
};

Node tree[N * 4];

void init() {
    memset(tree,0,sizeof(tree));
    memset(num,0,sizeof(num));
}

void cal(int id) {
    tree[id].a = min(tree[id<<1].a,tree[id<<1|1].a);
}

void build(int l,int r,int id) {
    tree[id].l = l;
    tree[id].r = r;
    tree[id].a = 0;
    if(l == r) return ;
    int mid = (l + r)/2;
    build(l,mid,id<<1);
    build(mid+1,r,id<<1|1);
}

void updata(int w,int id) {
    if(tree[id]. l == w && tree[id].r == w) {
        tree[id].a = 1;return;
    }
    int mid = (tree[id].l + tree[id].r)/2;
    if(w <= mid) updata(w,id<<1);
    else updata(w,id<<1|1);
    tree[id].a = tree[id<<1].a + tree[id<<1|1].a;
}

int query(int l,int r,int id) {
    if(l <= tree[id].l && r >= tree[id].r)return tree[id].a;
    int mid = (tree[id].l + tree[id].r)/2;
    int ans1 = 0,ans2 = 0;
    if(l <= mid) ans1 = query(l,r,id<<1);
    if(r > mid) ans2 = query(l,r,id<<1|1);
    return ans1 + ans2;
}

int main() {

    int n;
    while(scanf("%d",&n) == 1) {
        init();
        build(1,n,1);
        int ans = 0;
        for(int i=0;i