#278. 【UTR #2】题目排列顺序

“又要出题了。” 宇宙出题中心主任 —— 吉米多出题斯基，坐在办公桌前策划即将到来的 UOI。

这场比赛有 nn 道题，吉米多出题斯基需要决定这些题目的难度，然后再在汪洋大海中寻找符合该难度的题目。

题目的难度可以用一个 11 到 nn 的排列 a1,…,ana1an 表示，其中 aiai 表示第 ii 道题目在这 nn 道题目中是第 aiai 简单的题目，即恰有 ai−1ai1 道题目比第 ii 道题目简单。

经验丰富的吉米多出题斯基早就悟出了一种科学地决定难度顺序的方法。首先，吉米多出题斯基定义了难度递增子序列为序列 ap1,ap2,…,apkap1ap2apk （1≤p1<p2<?<pk≤n1p1p2pkn） 满足 ap1<ap2<?<apkap1ap2apk 。然后，吉米多出题斯基决定了 nn 个整数 f1,…,fnf1fn，他希望找出一个难度顺序使得对于每个 1≤i≤n1in 均满足以 aiai 结尾的难度递增子序列的最长长度恰好为 fifi。

但吉米多出题斯基日理万机，于是他找到了你 —— 风璃殇做不出题耶维奇，请你帮助吉米多出题斯基构造一个符合条件的 a1,…,ana1an 吧！

输入

第一行一个正整数 nn。

接下来一行 nn 个数，其中第 ii 个数表示 fifi。（1≤fi≤n1fin）

输出

输出一行 nn 个数，表示 a1,…,ana1an。

题目保证至少存在一组解。如有多组解，输出任意一组均可。

样例一

input

7
1 1 1 1 1 1 1

output

7 6 5 4 3 2 1

explanation

以每个 aiai 结尾的最长难度递增子序列分别为 {7},{6},{5},{4},{3},{2},{1}7654321。

样例二

input

7
1 2 3 2 4 4 3

output

1 4 5 2 7 6 3

explanation

以每个 aiai 结尾的最长难度递增子序列分别为 {1},{1,4},{1,4,5},{1,2},{1,4,5,7},{1,4,5,6},{1,2,3}1141451214571456123。

限制与约定

时间限制：1s1s

空间限制：256MB256MB

难得的大水题啊～～～

#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<utility>
#include<map>
#include<set>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<sstream>
#include<cstring>
#include<bitset>
#include<stack>
using namespace std;

int n,ans[100005];
struct sdt
{
	int num,pos;
}a[100005];

bool cmp(sdt x,sdt y)
{
	if(x.num!=y.num)return x.num<y.num; else return x.pos>y.pos;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].num;
		a[i].pos=i;
	}
	sort(a+1,a+1+n,cmp);
	
	for(int i=1;i<=n;i++)ans[a[i].pos]=i;
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}

UOJ #278. 【UTR #2】题目排列顺序(排序水题)

原文：http://www.cnblogs.com/winmt/p/6268937.html