本题题意很简单,就是给你一个N-1的序列,表示从第二个数开始,这个数前面有多少个比自己小的数。求这个序列。
这题一开始我以为是组合数学的逆序列,不过其实也差不多。后来想了一个算法不过错了,那就不说了。这个算法是o(n^2)的算法
如果数据强的话会超时。就是如果这个数前面有m个比自己小的,那么我就假设其为m+1,然后判断前面有没有出现过m+1,如果有,那么把所有大于等于m+1的数都加1.注意第一个数先设为1.很水的题目,搞了半天,还是要好好学习啊!
代码:
#include<stdio.h>
#define N 8010
int num[N],to[N],n;
void solve()
{
int i,j,k;
to[1]=1;
for(i=2;i<=n;i++)
{
to[i]=num[i]+1;
for(j=1;j<i;j++)//寻找前面是否出现过此数
{
if(to[j]==to[i])
break;
}
if(j<i)//如果出现加1
{
for(k=1;k<i;k++)
{
if(to[k]>=to[i])
to[k]++;
}
}
}
}
int main()
{
int i,j=0;
scanf("%d",&n);
for(i=2;i<=n;i++)
scanf("%d",&num[i]);
num[1]=0;
solve();
for(i=1;i<=n;i++)
printf("%d/n",to[i]);
return 0;
}