Home PAT 1056 Mice and Rice
Post
Cancel

PAT 1056 Mice and Rice

Link

题目不难, 也可以用队列做. 就是有个地方会忽略, 在下面代码的注释中标注出来了.

想要看更完整、更全面的测试用例, 可以去 牛客 上提交.

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
72
73
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int np,ng;
int w[1000],num[1000],rk[1000];
vector<int>group;
struct node{
    int id,rank;
}arr[1000],brr[1000];
bool cmp1(const node&a,const node&b){
    return a.rank<b.rank;
}
bool cmp2(const node&a,const node&b){
    return a.id<b.id;
}
int main() {
    scanf("%d%d",&np,&ng);
    for(int i=0;i<np;++i)
        scanf("%d",&w[i]);
    for(int i=0;i<np;++i){
        scanf("%d",&num[i]);
        group.push_back(num[i]);
    }
    if(ng==1){
        for(int i=0;i<np;++i)
            arr[i]={i,w[i]};
        sort(arr,arr+np,cmp1);
        for(int i=0;i<np;++i)
            arr[i].rank=np-i;
        sort(arr,arr+np,cmp2);
        for(int i=0;i<np;++i){
            if(i!=0) printf(" ");
            printf("%d",arr[i].rank);
        }
        return 0;
    }
    int cnt=1;
    while(group.size()>1){
        vector<int>temp;
        for(int i=0;i<group.size();i+=ng){
            int maxv=w[group[i]],cur=group[i];
            for(int j=i+1;j<i+ng&&j<group.size();++j)
                if(w[group[j]]>maxv){
                    maxv=w[group[j]];
                    cur=group[j];
                }
            rk[cur]++;
            temp.push_back(cur);
        }
        group=temp;
        cnt++;
    }
    for(int i=0;i<np;++i)
        arr[i]={i,cnt-rk[i]};
    sort(arr,arr+np,cmp1);
    //这里很容易弄错!不要在原数组arr上修改rank!不然前面arr[i-1].rank改了可能会比arr[i].rank大,然后就会造成一连串的错误!
    brr[0]=arr[0];
    for(int i=1;i<np;++i)
        if(arr[i].rank>arr[i-1].rank) brr[i]={arr[i].id,i+1};
        else brr[i]={arr[i].id,brr[i-1].rank};
    sort(brr,brr+np,cmp2);
    for(int i=0;i<np;++i){
        if(i!=0) printf(" ");
        printf("%d",brr[i].rank);
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.