程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> uva 11525排列(樹狀數組 + 二分)

uva 11525排列(樹狀數組 + 二分)

編輯:關於C++
 現在給定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;
}











 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved