ACM: 强化训练-Inversion Sequence-线段树 or STL·vector

Inversion Sequence

Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%lld & %llu

Description

For sequence i1, i2, i3, … , iN, we set aj to be the number of members in the sequence which are prior to j and greater to j at the same time. The sequence a1, a2, a3, … , aN is referred to as the inversion sequence of the original sequence (i1, i2, i3, … , iN). For example, sequence 1, 2, 0, 1, 0 is the inversion sequence of sequence 3, 1, 5, 2, 4. Your task is to find a full permutation of 1~N that is an original sequence of a given inversion sequence. If there is no permutation meets the conditions please output “No solution”.

Input

There are several test cases.
Each test case contains 1 positive integers N in the first line.(1 ≤ N ≤ 10000).
Followed in the next line is an inversion sequence a1, a2, a3, … , aN (0 ≤ aj < N)
The input will finish with the end of file.

Output

For each case, please output the permutation of 1~N in one line. If there is no permutation meets the conditions, please output “No solution”.

Sample Input

5

1 2 0 1 0

3

0 0 0

2

1 1

Sample Output

3 1 5 2 4

1 2 3

No solution

这题有两种做法，一开始直接用STL里的vector A掉了这个题目，然后基神让我试下用线段树来解这个题目，我就两种方法都写了

先来线段树： 从小到大插入到第k个格子。

/*/

线段树做法：

首先，弄个长度为n的线段树，维护sum，初始值为1

那么，sum[1]等于n，代表着空着的位置的数量

现在要把某个数字插入到p位置，就在线段树找到一个位置x，使得[x]里面的sum等于p；

然后把那个1修改为0，就表示那个位置不是空着的了。 

/*/ 

#include"iostream"

#include"cstdio"

#include"cstring"

#include"algorithm"

#include"cmath"

using namespace std;

#define MX 11111

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

int sum[MX<<2];

void PushUp(int rt) {

	sum[rt]=sum[rt<<1]+sum[rt<<1|1];

}

void Build(int l,int r,int rt) {

	sum[rt]=1;

	if(r==l)return ;

	int m=(r+l)>>1;

	Build(lson);

	Build(rson);

	PushUp(rt);

}

int Query(int p,int l,int r,int rt) {

	if(l==r) {      	//找到点，插入，返回点的位置值

		sum[rt]--;

		return l;

	}

	int m=(l+r)>>1,ret=0;

	if(p<=sum[rt<<1]) ret=Query(p,lson);//点在左边，直接向左找

	else ret=Query(p-sum[rt<<1],rson);// 减去左边没去找的点

	PushUp(rt);

	return ret;

}

int a[MX];

int ans[MX];

int main() {

	int n;

	while(~scanf("%d",&n)) {

		Build(1,n,1);

		for(int i=1; i<=n; i++) {

			scanf("%d",&a[i]);

		}

		bool check=1;

		for(int i=1; i<=n; i++) {

			if(sum[1]<a[i]+1) {

				check=0;

				break;

			} else {

				int p= Query(a[i]+1,1,n,1);

				ans[p]=i;

			}

		}

		if(!check)printf("No solution\n");

		else {

			int first=1;

			for(int i=1; i<=n; i++) {

				if(first)first=0;

				else printf(" ");

				printf("%d",ans[i]);

			}

			printf("\n");

		}

	}

	return 0;

}

　　

然后是STL：  从大到小插入到第k个格子。

/*/

STL-vector:

从最大的数开始插入队列；

利用vector中的insert()函数去将数字插入相应的位置；

这种方法暴力，简单。。。

但是每一次插入复杂度是O(n);

数据有点放水，还是A了。

/*/

#include"iostream"

#include"cstdio"

#include"cstring"

#include"string"

#include"algorithm"

#include"vector"

using namespace std;

#define MX 10050

int num[MX];

int main() {

	int n;

	while(~scanf("%d",&n)) {

		for(int i=0; i<n; i++) {

			scanf("%d",&num[i]);

		}

		int flag=1;

		vector<int > v;

		v.push_back(0);

		for(int i=n-1;i>=0; i--) {

			if(v.size()<=num[i]) {

				printf("No solution\n");

				flag=0;

				break;

			}

			v.insert(v.begin()+num[i],i+1);

		}

		if(flag) {

			int first=1;

			vector<int>::iterator it;

			for(it=v.begin(); it!=v.end()-1; it++) {

				if(first) {

					first=0;

					printf("%d",(*it));

				}

				else printf(" %d",(*it));

			}

			printf("\n");

		}

	}

	return 0;

}

　　

ACM: 强化训练-Inversion Sequence-线段树 or STL·vector的相关教程结束。