7-10 stack of hats (25 points) (C language solution)

PATers believe that wearing hats makes them look handsome, so wherever they go, everyone of them would wear a hat. One day they came to a restaurant, a waiter collected their hats and piled them up. But then when they were ready to leave, they had to face a stack of hats as shown by the above figure. So your job is to help them line up so that everyone can pick up his/her hat one by one in order without any trouble.

It is known that every hat has a unique size, which is related to the weight of its owner -- that is, the heavier one wears larger hat.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number N (≤104) which is the number of PATers. The next line gives N distinct sizes of the hats, which are positive numbers no more than 105. The sizes correspond to the hats from bottom up on the stack. Finally in the last line, N distinct weights are given, correspond to the hat owners numbered from 1 to N. The weights are positive numbers no more than 106. All the numbers in a line are separated by spaces.

Output Specification:

For each test case, print in a line the indices of the hat owners in the order of picking up their hats. All the numbers must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

10
12 19 13 11 15 18 17 14 16 20
67 90 180 98 87 105 76 88 150 124

Sample Output:

3 4 8 6 10 2 1 5 9 7

Hint:

The 1st hat has the largest size 20, hence must correspond to the one with the largest weight, which is the 3rd one of weight 180. So No.3 must go first.

The 2nd hat has the 6th smallest size 16, hence corresponds to the 6th smallest weight, which is 98. So No.4 is the next to go.

And so on so forth.

vernacular ： It's a pile of hats distributed from top to bottom , Big hats are for heavy people , At the same time, feedback the person's subscript .

Because the big one needs to be given to the big one , So we definitely need to work on size comparison , However , What I have learned so far , Sorting requires data transformation , Then we need to create an array at this time , Let him store the corresponding data, sorted , Considering that we need both ranking and the corresponding position of the data , We define two new arrays , After storing the data of shoes or people's weight , At the same time, there is a structure variable to store their original location , I was thinking about recording the size of the hat and the weight of the person rank And then it went out of time , So it was transformed , We just need to compare the ranking of hats （ At this time, the data of hat type has been sorted ）, People's weight is also ranked , here The ranking of hat number is the serial number of the corresponding person sorted by weight , Simultaneous human rank Used to store their original subscripts （ there rank Refer to person Of rank.）, Finally, output the subscript . I also thought about it. If I don't rank the hat , Give Way rank It's also to count their original subscripts , But one of the troubles is , We need to find the element corresponding to the subscript （ After sorting ）, That is to say, we need to traverse , But this undoubtedly increases the time complexity , So let's find a number rank, Finally, it passed .

Code up ：

#include <stdio.h>
typedef struct{
    int hp;
    int rank;
}ss;
int main(){
    int N;
    scanf("%d",&N);
    ss s[N+1];
    ss p[N+1];
    ss o[N+1];
    ss q[N+1],temp;
    int i,j,n=0;
    for(i=1;i<N+1;i++)scanf("%d",&s[i].hp);
    for(i=1;i<N+1;i++)scanf("%d",&o[i].hp);
    for(i=1;i<N+1;i++){p[i]=s[i];p[i].rank=i;}
    for(i=1;i<N+1;i++){q[i]=o[i];q[i].rank=i;}
    for(i=1;i<N+1;i++){
        for(j=i+1;j<N+1;j++){// Rank according to the size of shoes 
            if(p[i].hp<p[j].hp){
                temp=p[i];
                p[i]=p[j];
                p[j]=temp;
            }
        }
    }
    for(i=1;i<N+1;i++){// Count out the current ranking of the shoes corresponding to each shoe 
    	for(j=1;j<N+1;j++){
    		if(p[i].hp==s[j].hp){
    			s[j].rank=++n;
    			break;
			}
		}
	}
	    for(i=1;i<N+1;i++){// Rank everyone's weight 
        for(j=i+1;j<N+1;j++){
            if(q[i].hp<q[j].hp){
                temp=q[i];
                q[i]=q[j];
                q[j]=temp;
            }
        }
    }
    n=0;
    for(i=N;i>0;i--){//person The corresponding structure ss Medium rank Is to record the subscript function , and hat Inside rank Is true rank That is, ranking .
     			if(i!=1)printf("%d ",q[s[i].rank].rank);// Print out the corresponding format .
     			else printf("%d\n",q[s[i].rank].rank);
    }
}