首页 > ACM题库 > HDU-杭电 > hdu 2404 Permutation Recovery-线段树-[解题报告]hoj
2014
01-26

hdu 2404 Permutation Recovery-线段树-[解题报告]hoj

Permutation Recovery

问题描述 :

Professor Permula gave a number of permutations of the n integers 1, 2, …, n to her students. For each integer i (1 <= i <= n), she asks the students to write down the number of integers greater than i that appears before i in the given permutation. This number is denoted ai. For example, if n = 8 and the permutation is 2,7,3,5,4,1,8,6, then a1 = 5 because there are 5 numbers (2, 7, 3, 5, 4) greater than 1 appearing before it. Similarly, a4 = 2 because there are 2 numbers (7, 5) greater than 4 appearing before it.

John, one of the students in the class, is studying for the final exams now. He found out that he has lost the assignment questions. He only has the answers (the ai’s) but not the original permutation. Can you help him determine the original permutation, so he can review how to obtain the answers?

输入:

The input consists of a number of test cases. Each test case starts with a line containing the integer n (n <= 500). The next n lines give the values of a1, …, an. The input ends with n = 0.

输出:

The input consists of a number of test cases. Each test case starts with a line containing the integer n (n <= 500). The next n lines give the values of a1, …, an. The input ends with n = 0.

样例输入:

8
5
0
1
2
1
2
0
0
10
9
8
7
6
5
4
3
2
1
0
0

样例输出:

2,7,3,5,4,1,8,6
10,9,8,7,6,5,4,3,2,1


/*题意:有1->n n个数字,告诉你每个数字前有多少个数字比它大,让你求原来的序列做法:数字i之前有k个数字比它大的话,那么i应该在剩下的第k+1个空位上。然后就可以线段树了,统计区间数字书目。 */#include<iostream>using namespace std;struct node{       int l,r;       int num;}tr[501*4];void build(int index,int l,int r){     tr[index].l=l,tr[index].r=r;     tr[index].num=tr[index].r-tr[index].l+1;     if ( l==r ) return;     build(index*2,l,(l+r)/2);     build(index*2+1,(l+r)/2+1,r);}int update(int index,int num){     if ( tr[index].l==tr[index].r )      {          tr[index].num=0;          return tr[index].l;     }     int ans;     if ( num<=tr[index*2].num ) ans = update(index*2,num);     else ans = update(index*2+1,num-tr[index*2].num);     tr[index].num=tr[index*2].num+tr[index*2+1].num;     return ans;}int main(){    int n,i,val,pos[501];    while ( scanf("%d",&n)!=EOF && n )    {          build(1,1,n);          for ( i=1;i<=n;i++ )          {              scanf("%d",&val);              int tmp = update(1,val+1);              pos[tmp]=i;          }          for ( i=1;i<=n;i++ )          {              if ( i==1 ) printf("%d",pos[i]);              else printf(",%d",pos[i]);          }          printf("\n");    }    return 0;}                             
解题参考:http://hi.baidu.com/ccsuxmq/item/57854623b055e2f651fd8769


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.