当前位置:网站首页>7-10 stack of hats (25 points) (C language solution)
7-10 stack of hats (25 points) (C language solution)
2022-07-03 14:33:00 【Study hard 867】
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);
}
}
边栏推荐
- Leetcode (4) - - trouver la médiane de deux tableaux ordonnés positifs
- Similarities and differences between Allegro, OrCAD, net alias, port, off page connector and how to select them
- 【7.3】146. LRU caching mechanism
- tonybot 人形机器人 定距移动 代码编写玩法
- 7-17 crawling worms (break exercise)
- Four data flows and cases of grpc
- Although not necessarily the best, it must be the hardest!
- X86 assembly language - Notes from real mode to protected mode
- ZABBIX saves the page blank after adding calculated items
- [qingniaochangping campus of Peking University] in the Internet industry, which positions are more popular as they get older?
猜你喜欢
adc128s022 ADC verilog设计实现
Understanding of closures
ConstraintLayout 的使用
一文了解微分段应用场景与实现机制
Four data flows and cases of grpc
pyQt界面制作(登录+跳转页面)
Zhonggan micro sprint technology innovation board: annual revenue of 240million, net loss of 17.82 million, proposed to raise 600million
x86汇编语言-从实模式到保护模式 笔记
泰凌冲刺科创板:拟募资13亿 国家大基金与小米长江是股东
Analysis of gene family characteristics - chromosome location analysis
随机推荐
Paper sharing: generating playful palettes from images
Get permissions dynamically
Exercise 6-6 use a function to output an integer in reverse order
Luogu p5194 [usaco05dec]scales s solution
ConstraintLayout 的使用
protobuf与grpc
Mysql多表查询 #子查询
pyQt界面制作(登录+跳转页面)
Jiuyi cloud black free encryption free version source code
MongoDB索引
7-24 reduction of the simplest fraction (rolling Division)
天谋科技 Timecho 完成近亿元人民币天使轮融资,打造工业物联网原生时序数据库
Understand the application scenario and implementation mechanism of differential segment
亚马逊、速卖通、Lazada、Shopee、eBay、wish、沃尔玛、阿里国际、美客多等跨境电商平台,测评自养号该如何利用产品上新期抓住流量?
论文分享:Generating Playful Palettes from Images
fpga阻塞赋值和非阻塞赋值
动态获取权限
Puzzle (016.4) domino effect
Leetcode (4) - - trouver la médiane de deux tableaux ordonnés positifs
Selective sorting