PAT 1056

题目 ： Mice and Rice

分值 ： 25
难度 ： 难题
思路 ： 场景模拟，每K个老鼠比一下决出冠军进入下一轮，如此循环直到第一名产生
坑点 ： 这个模拟很难写，因为有一个比赛晋级的过程模拟，我这里用data存放顺序选手，然后按照
       题目所给的顺序弄了一个list数组，每轮有J个选手，每K个比一次，每一个选手名次都是 
       （J+K-1)/K+1 ;然后每K个里面最大的那一个重新放到list的前面，J每经过一轮都会变
       J = （J+K-1)/K  ; 直到只剩下一个；关键问题是你每次重新组成list的时候，他们的
       rank信息不能直接记录在 list[i].rank 里面，因为list只是一个临时数组，你每一轮
       都会扔掉前一轮的list数据，因此你需要从list[i].self 获取信息，然后更新到data
       当中去，data数组是各个选手的数组，是不会被扔掉的。
评语 ： 虽然过程很痛苦，但是还是一次AC了

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
using namespace std ;
typedef struct Node{
    int self ;
    int value ;
    int rank ;
}Nodes;
Nodes data[1001];
Nodes list[1001];
bool cmp(Node a , Node b )
{
    return a.self< b.self ;
}
int main() {
    int N , K ;
    cin >> N >>K ;
    for(int i = 0 ; i< N ; i++)
    {
        data[i].self = i ;
        cin >>data[i].value ;
    }
    int temp ;
    for(int i = 0 ; i< N ; i++)
    {
        cin >> temp ;
        list[i] = data[temp] ;
    }

    int cnt = 0 , max = 0 ,index ;
    int cur = 0 ;
    int j = N ;
    while(j>1)
    {
        cur = 0 ;
        max = 0 ;
        for(int i = 0 ; i< j ; i++)
        {
            if(list[i].value >= max)
            {
                max = list[i].value;
                index = i ;
            }
            cnt++ ;
            if(cnt ==K )
            {
                cnt = 0 ;
                max = 0 ;
                list[cur++] = list[index] ;
            }
            int xx = list[i].self ;
            data[xx].rank = (j+K-1) /K +1  ; //这一轮晋级的人数
           // list[i].rank = (j+K-1) /K +1  ; //这一轮晋级的人数
        }
        if(cnt)
        {
            list[cur++] = list[index] ;
            cnt = 0 ;
        }
        j= (j+K-1)/K ;
    }
    int xx = list[index].self ;
    data[xx].rank =1  ; //这一轮晋级的人数
    //sort(list,list+N , cmp) ;
    for(int i = 0 ; i < N ; i++)
    {
        if(i)
            cout <<" " ; 
        cout <<data[i].rank;
    }

}