Ordering the Soldiers 题解

CodeChef:ORDERS

简化题意：

\(n\) 个人排队，给定每个人需要向左移动几个，求最终排列。

即还原逆序对。

错误想法

既然知道每个人向左移动 \(a_i\) 个，那就相当于让他的排名 \(-a_i\)，他前面 \(a_i\) 个人的排名 \(+1\)，差分即可。

问题在于他前面的 \(a_i\) 应是前面的人排好后的后 \(a_i\) 个，直接差分则是原序列中的。

sol

考虑倒着做。最后一个人的排名显然是 \(n-a_n\)，则第 \(n-1\) 个人则是剩余排名中第 \(n-1-a_{n-1}\) 小的，以此类推。

正确性：分两类：第 \(n\) 个人是否对第 \(n-1\) 个人有影响易证。

code

const int N = 2e6+5;

int T,n;

int a[N],b[N];

#define lb(x) (x&-x)

struct BIT {

	int t[N],n,l;

	void add(int i,int x){for(;i<=n;i+=lb(i))t[i]+=x;}

	int kth(int k) { // 权值BIT求第k大

		int res = 0;

		for(int i = l; ~i; --i) {

			res += 1<<i;

			if( res > n || k-t[res] <= 0 ) res -= 1<<i;

			else k -= t[res];

		}

		return res+1;

	}

} bit;

#undef lb

int main() {

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	read(T);

	while( T-- ) {

		read(n);

		bit.n = n;

		for(bit.l = 1; (1<<bit.l+1) <= n; ++bit.l);

		For(i,1,n) read(a[i]), bit.add(i,1);

		for(int i = n; i; --i) {

			b[i] = bit.kth(i-a[i]);

			bit.add(b[i],-1);

		}

		For(i,1,n) printf("%d ",b[i]);

		putchar(10);

	}

	return 0;

}

巴特西

Ordering the Soldiers 题解

简化题意：

错误想法

sol

最新文章

热门文章