当前位置:网站首页>PAT_ Grade A_ 1056 Mice and Rice

PAT_ Grade A_ 1056 Mice and Rice

2020-11-08 16:59:01 Qiao Zixin

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 :

 picture .png

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 :

 picture .png

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;
}

版权声明
本文为[Qiao Zixin]所创,转载请带上原文链接,感谢