1056 Mice and Rice

发表于

输入n为老鼠数量，g为每一组老鼠的最大值，之后从0到n-1个老鼠的体重，最后是老鼠体重的比较序列。
对于每一组老鼠，选出最重的那个，晋级下一轮，本轮的其他老鼠名次相同，直到选出第一名。

结构体node表示老鼠，里面包括weight重量，index是按照排名后的顺序的老鼠的下标，index0是排名前老鼠的下标。rank是最终要输出的老鼠的排名。

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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int weight, index, rank, index0;
};
bool cmp1(node a, node b) {
    return a.index0 < b.index0;
}
int main() {
    int n, g, num;
    scanf("%d%d", &n, &g);
    vector<int> v(n);
    vector<node> w(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    for(int i = 0; i < n; i++) {
        scanf("%d", &num);
        w[i].weight = v[num];
        w[i].index = i;
        w[i].index0 = num;
    }
    queue<node> q;
    for(int i = 0; i < n; i++)
        q.push(w[i]);
    while(!q.empty()) {
        int size = q.size();
        if(size == 1) {
            node temp = q.front();
            w[temp.index].rank = 1;
            break;
        }
        int group = size / g;
        if(size % g != 0)
            group += 1;
        node maxnode;
        int maxn = -1, cnt = 0;
        for(int i = 0; i < size; i++) {
            node temp = q.front();
            w[temp.index].rank = group + 1;
            q.pop();
            cnt++;
            if(temp.weight > maxn) {
                maxn = temp.weight;
                maxnode = temp;
            }
            if(cnt == g || i == size - 1) {
                cnt = 0;
                maxn = -1;
                q.push(maxnode);
            }
            // 把本组的获胜者放入比较队列，并且重置准备检查下一组
        }
    }
    sort(w.begin(), w.end(), cmp1);
    for(int i = 0; i < n; i++) {
        if(i != 0) printf(" ");
        printf("%d", w[i].rank);
    }
    return 0;
}

另一个参考：

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
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, m, x;
    cin >> n >> m;
    vector<int> mice(n);
    vector<int> order(n);
    int rank[n];
    fill(rank,rank+n,0);
    
    for (int i = 0; i < n; ++i) {
        cin>>mice[i];
    }
    for (int i = 0; i < n; ++i) {
        cin>>order[i];
    }
    vector<int> res;
    int Max, idex, group;
    while (order.size()>1) {
        group = order.size() / m + 1;
        if ((order.size() % m != 0) ) ++group;
        for (int i = 0; i < order.size(); ++i) {
            if (i%m == 0) {
                Max = -1;
                if (i != 0) {
                    res.push_back(idex);
                }
            }
            if (Max < mice[order[i]]) {
                Max = mice[order[i]];
                idex = order[i];
            }
            rank[order[i]] = group;
        }
        res.push_back(idex);
        order = res;
        res.clear();
    }
    rank[order[0]] = 1;
    for (int i = 0; i < n; ++i) {
        if (i != 0) cout << ' ';
        cout << rank[i];
    }
    return 0;
}

原文链接：https://blog.csdn.net/CV_Jason/java/article/details/85238006