PTA A_1056 Mice and Rice

798236606

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805419468242944

解:
队列

1. #include<cstdio>
   
2. #include<queue>
   
3. 
   
4. using namespace std;
   
5. 
   
6. struct{
   
7.     int weight, rank;
   
8. }mouse[1010];
   
9. 
   
10. int main(void)
    
11. {
    
12.     int np, ng;
    
13.    
    
14.     scanf("%d %d", &np, &ng);
    
15.    
    
16.     queue<int> q;
    
17.    
    
18.     for (int i = 0; i < np; i++)
    
19.         scanf("%d", &mouse[i].weight);
    
20.         
    
21.     for (int i = 0; i < np; i++)
    
22.     {
    
23.         int order;
    
24.         
    
25.         scanf("%d", &order);
    
26.         q.push(order);
    
27.     }
    
28.    
    
29.     int len;
    
30.     while ((len = q.size()) > 1)
    
31.     {
    
32.         int group = (len % ng) ? (len / ng + 1) : (len / ng);
    
33.         
    
34. //      printf("group = %d, ", group);
    
35.         for (int i = 0; i < group; i++)
    
36.         {
    
37.             int winer = q.front();
    
38.             
    
39.             for (int j = 0; j < ng && (i * ng + j) < len; j++)
    
40.             {
    
41.                 mouse[q.front()].rank = group + 1;
    
42.                
    
43.                 if (mouse[q.front()].weight > mouse[winer].weight)
    
44.                     winer = q.front();
    
45.                
    
46. //              printf("%d ", mouse[q.front()].weight);
    
47.                 q.pop();
    
48.             }
    
49.             
    
50.             q.push(winer);   
    
51.         }
    
52.         
    
53. //      putchar('\n');
    
54.     }
    
55.    
    
56.     mouse[q.front()].rank = 1;
    
57.    
    
58.     for (int i = 0; i < np; i++)
    
59.     {
    
60.         printf("%d", mouse[i].rank);
    
61.         
    
62.         if (i < np - 1)
    
63.             putchar(' ');
    
64.     }
    
65.    
    
66.     return 0;   
    
67. }
    

复制代码