程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 11525排列（樹狀數組 + 二分）

uva 11525排列（樹狀數組 + 二分）

編輯：C++入門知識

uva 11525排列（樹狀數組 + 二分）

現在給定k和n，要你按字典序輸出第n種排列的數列

而且題目給的 n是 n=S1（k-1）！+S2(k-2)!+...+Sk-1*1!+Sk*0!(0=

我們可以知道si表示i後面有多少個比a[i]小的數，這樣一來首先想到的就是set，但是set不能順序訪問，所以可以用樹狀數組，初始時置1，消除後置0，然後二分來求和為si + 1的位置

代碼如下：

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
using namespace std;  
#define LL long long  
const int maxn = 50005;
const int INF = 1000000000;
//freopen("input.txt", "r", stdin);

int c[2 * maxn], s[maxn], ans[maxn], k;

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

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

void add(int x) {
	while(x <= k) {
		c[x] += 1; x += lowbit(x);
	}
}

void subtract(int x) {
	while(x <= k) {
		c[x] -= 1; x += lowbit(x);
	}
}

int main() {
	int t; scanf("%d", &t);
	while(t--) {
		memset(c, 0, sizeof(c));
		cin >> k;
		for(int i = 1; i <= k; i++) add(i);
		
		for(int i = 1; i <= k; i++) {
			int tmp; cin >> tmp;
			int le = 1, ri = k;
			while(le < ri) {
				int mi = (le + ri) >> 1;
				int tsum = sum(mi);
				if(sum(mi) >= tmp + 1) ri = mi;
				else le = mi + 1;
			}
			ans[i] = ri;
			subtract(ans[i]);
		}
		printf("%d", ans[1]);
		for(int i = 2; i <= k; i++) printf(" %d", ans[i]);
		printf("\n");
	}
	return 0;
}