The main idea of the topic :
give NP The quality of a mouse , And give the order in which they play , Then each NG A group of mice , In the end, it's not enough NG Only for a group , And then the competition within the group , The heaviest winner enters the next round , The rankings lost in this round are the same , The output is required to be ranked according to the number from small to large , Here we have to pay attention to the meaning of the title , That is the first. 3 The data given , This is actually a mouse subscript , Then the output is in the order of 0 To NP-1 The order of
Algorithm ideas ：
Example interpretation ：
First of all, make it clear , Given the initial number of participants and the number of people in each group , You can know exactly how many times you play ( Rounds ) And after every game , The position of the loser .
For the specific number of games to get the following code ：
int round = 1;// Total rounds
// Calculate the total rounds
while(NP!=1){
if(NP%NG==0){
NP = NP/NG;
}else {
NP = NP/NG + 1;
}
++round;
}The following code is used to get the position of the loser in each game ：
int round = 1;// Total rounds
// Calculate the total rounds and the ranking of the losers in each competition
while(NP!=1){
if(NP%NG==0){
NP = NP/NG;// At present round The round has NP Individual wins , Indicates the current round of loser There is NP personal , Their rankings are all NP+1
}else {
NP = NP/NG + 1;
}
rankByRound[round] = NP+1;
++round;
}
rankByRound[round] = 1;// Record the last round of rankings It's used here round Record the total number of games ,rankByRound The array records the positions of the losers in each round . Then we save the number of participants in each competition in a queue ,queue<int> q[currentRound] The number of current rounds is saved , And then there's the simulation of the game , We use popNum Record the number of people who have participated in the current round ,size Record the total number of players in the current round , If size==1 It means there's only one person , You can assign the ranking directly , otherwise , as long as popNum<size It means that the current game is not over yet , let needPop Record the number of teams in the current game , And then in needPop Choose the person with the largest weight as winner, Join the next round of competition q[currentRound+1].push(winner); . All losers will be ranked and returned to the current queue (rank[loser] = rankByRound[currentRound];q[currentRound].push(loser)). Remember to update popNum and currentRound, Finally, output the ranking .
Be careful ：
1、 When there's only one person in the queue, a special judge is needed , Just exit the cycle directly .
2、 If the test point 5 Run timeout , Consider changing the way you get rankings , Detailed see AC Code 1. If you don't want to change the way you get rankings , You can refer to AC Code 2.
Submit results ：
Here is given 2 Different ways of implementation , The main difference is in the way you get rankings ,AC Code 1 Used to calculate the ranking of all rounds first , In every round of competition , Rank the losers .AC Code 2 Instead, it traverses the ranking assignment operation of each queue finally .AC Code 1 Using the remaining elements of the traversal queue to get the ranking will cause the last test point to time out .
AC Code 1：
#include<cstdio>
#include<queue>
using namespace std;
queue<int> q[15];// Each round is stored in a queue
int main(){
int NP,NG;// The number of programmers and the most NG A group of mice
scanf("%d %d",&NP,&NG);
int weight[NP];// The weight of each mouse
int rank[NP];// The final ranking of each mouse
int rankByRound[NP];// The ranking of the losers in each round
for(int i=0;i<NP;++i){
scanf("%d",&weight[i]);
}
int currentRound = 1;// The current round of the game
// Initialize the competition object
int order;
for(int i=0;i<NP;++i){
scanf("%d",&order);
q[currentRound].push(order);
}
int n = NP;
int round = 1;// Total rounds
// Calculate the total rounds and the ranking of the losers in each competition
while(NP!=1){
if(NP%NG==0){
NP = NP/NG;// At present round The round has NP Individual wins , Indicates the current round of loser There is NP personal , Their rankings are all NP+1
}else {
NP = NP/NG + 1;
}
rankByRound[round] = NP+1;
++round;
}
rankByRound[round] = 1;// Record the last round of rankings
// The game begins
while(currentRound<=round){
int popNum = 0;// The number of people out of the team
int size = q[currentRound].size();// The number of participants in the current round
if(size==1){
// The current round is the last round , There's no need to compete , You can assign the ranking directly
rank[q[currentRound].front()] = rankByRound[currentRound];
break;
}
while(popNum<size){
int needPop = size-popNum>=NG?NG:size-popNum;// Need to be out of the team
int winner = q[currentRound].front();// First save the team leader element as the winner
q[currentRound].pop();
++popNum;
for(int i=0;i<needPop-1;++i){
// In the remaining needPop-1 The one who gets the most weight among the players
if(weight[winner]<weight[q[currentRound].front()]){
// Team leader element wins , First of all, will winner Join the queue , And then update winner
rank[winner] = rankByRound[currentRound];// to loser Assign the current rank
q[currentRound].push(winner);
winner = q[currentRound].front();
q[currentRound].pop();
} else {
// The team leader lost , Add the team leader element to the end
int loser = q[currentRound].front();
rank[loser] = rankByRound[currentRound];// to loser Assign the current rank
q[currentRound].pop();
q[currentRound].push(loser);
}
++popNum;
}
// Add the winner to the next round
q[currentRound+1].push(winner);
}
++currentRound;
}
// Output ranking
for(int i=0;i<n;++i){
printf("%d",rank[i]);
if(i<n-1) printf(" ");
}
return 0;
} AC Code 2：
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
/*
Subject requirements : give NP The quality of a mouse , And give the order in which they play , Then each NG A group of mice , In the end, it's not enough NG Only for a group , And then the competition within the group , The heaviest winner enters the next round , This round of competition lost
The rankings are the same , The output is required to be ranked according to the number from small to large , Here we have to pay attention to the meaning of the title , That is the first. 3 The data given , This is actually a mouse subscript , Then the output is in the order of 0 To NP-1 The order of
Algorithm ideas : Here's your manuscript , Easy to understand , It's a simulation topic ( I hate this kind of stuff )
The first round (0): 6 0 (8)( The first group ,8 win victory ) ,(7) 10 5( The second group ,7 win victory ),(9) 1 4( The third group ,9 win victory ),2 (3)( The first 4 Group ,3 win victory )
The second round (1): (8) 7 9( The first group ,8 win victory ),(3)( The second group , Just one ,3 win victory )
The third round (2): (8) 3( The first group ,8 win victory )
The fourth round (3): (8)( The first group , Only one game is over )
1. Data storage : Use w,order The array stores the number of mice per mouse and the initial order of the game ,rank The array records the ranking of the last mouse ,queue<int> v[1000] Save the losers of each round , The final round was the winner
turn Record the current round of the game , For the initial 0( The same as the brackets at the end of the last round )
2. The starting order of the game is saved in v[0] in , Then simulate each round of the game , We use count Record the number of mice left in each round , The reason is that we're going to put the mice that lost the game back into the team , Keep out of the team
error , So as long as count!=0 That means the current round is not over yet , Use vector<int> a Save the current team's mouse index , The goal is to find the index of the current largest mouse weight , And then just count>=ng Just out of the team
ng A mouse came into a in , Or you're out of the team count A mouse ( Remember that you can't judge if the queue is empty , Because the mice that lost after the previous team's game have rejoined the team ), Then traverse a Array to get the weight of the largest mouse maxW,
Finally, we go through it again a, As long as the weight of the current mouse is not equal to maxW, It's a loser , Just go back into the present v[turn] queue , Otherwise, it's going to the next round v[turn+1], At the end of the current round ,++turn Go to the next round
match , And the number of mice in the current round is 1 When you exit the loop ( Because there are no mice to compare , The explanation is the final winner )
3. The acquisition of rankings : Traverse v Array , But it has to be traversed from the last round of the current round , Because the winner is the first one , When i==turn when , The explanation is number one , be rank[v[i].front()] = 1; Otherwise, all the mice in the current round
The number of mice in the front of the list num+1(num For the initial 0), Then update the number of mice in front of the next round num+=v[i].size()
4. Finally, output in order rank that will do
A little doubt :vector<queue<int> > v Can't use , and queue<int> v[1000] But you don't know why , Ask for advice
*/
queue<int> v[1000];// Save the losers of each round , The final round was the winner
int turn = 0;// The current round of the game
int main(){
int np,ng;// The total number of mice and the number of rats per team
scanf("%d %d",&np,&ng);
int w[np],order[np];// The weight of each mouse , The order of the game
int rank[np];// The final ranking
int count;// The number of mice left in each round
for(int i=0;i<np;++i){
scanf("%d",&w[i]);
}
for(int i=0;i<np;++i){
scanf("%d",&order[i]);
v[turn].push(order[i]);// Add the first round sequence to the queue
}
while(true){
count = v[turn].size();//count Start with all the mice in the current round
if(count==1){// Only one mouse in the current round indicates the end of the game
break;
}
while(count!=0){// The same round
vector<int> a;// Save the current team's mouse index
if(count>=ng){// The number of mice left is greater than or equal to ng, Just out of the team ng A mouse
for(int i=0;i<ng;++i){
a.push_back(v[turn].front());// Add the current team mouse to a in
v[turn].pop();
}
count -= ng;// to update count
}else{// There are not enough mice left ng individual , All the rest count A pair of mice
while(count!=0){
a.push_back(v[turn].front());
v[turn].pop();
--count;
}
}
int maxW=-1;// The weight of the heaviest mouse in the current team
int len = a.size();// The current number of teams
for(int i=0;i<len;++i){// Find the heaviest mouse in the current team
if(w[a[i]]>maxW){
maxW = w[a[i]];
}
}
for(int i=0;i<len;++i){
if(w[a[i]]!=maxW){// The loser enters and stays in the current round
v[turn].push(a[i]);
}else{// The winner enters the next round
v[turn+1].push(a[i]);
}
}
}
++turn;// Into the next round
}
int num = 0;// Record how many mice are in front of the current round
for(int i=turn;i>=0;--i){
int len = v[i].size();
for(int j=0;j<len;++j){// The first i The rest of the round queue are ranked the same
rank[v[i].front()] = num+1;
v[i].pop();
}
num += len;// Update to how many mice are in front of the next round of mice
}
for(int i=0;i<np;++i){
printf("%d",rank[i]);
if(i<np-1) printf(" ");
}
return 0;
}
