PAT甲级1056 Mice and Rice

原题链接PAT甲级1056 Mice and Rice

这道题,2020年7月份做的时候,做了好久才AC,今天又做了一次。使用了比较直观的思路,模拟了一遍题目。A掉了

题意

给了n只老鼠,以及每只老鼠的体重,注意题目告诉了,每只老鼠的体重满足== ​​ distinct non-negative numbers==,即不同的非负数,也就是说每只老鼠的体重不同,而且,并没有说是整数,所以对于每只老鼠的体重,最好是按照double型存放。做pat要对数据描述字眼敏感,没有说是整数,最好存储为double。

将每k只老鼠分为一组,最后不足k只的话,剩余的老鼠组成一组。
关于分组,又给出了顺序。其实是一开始谁和谁靠着,比如原始数据里面,第三行是顺序,也就是说一开始6号、0号、8号是靠着的三只,故它们三个要决出一个体重最大的胜者,进入下一轮。7、10、5号是靠着的,故它们三个要决出一个体重最大的胜者,进入下一轮。
9、1、4三只是靠着的,故它们三个要决出一个体重最大的胜者,进入下一轮。此时只剩下了2、3号两只老鼠不足3只,故故它们两个要决出一个体重最大的胜者,进入下一轮。

11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3

思路

使用结构体来存放每只老鼠的数据

struct mice{
    int id;//老鼠的id
    double weight;//老鼠的体重,double类型
    int rcnt,r;//rcnt为当前老鼠的轮数,r为老鼠的排名
    mice():rcnt(0){}//将每只老鼠的轮数的初始值设为0

    friend bool operator < (const mice &a,const mice &b){//重载 < 运算符,使用priority_queue
        return a.weight < b.weight;
    }
}mouse[1010];//定义一个mice类型的数组,大小为1010

读入数据,将每只老鼠的id按照顺序赋值为 i 。使用vector < int > ori 记录原始顺序。
ori中存放了当前轮的老鼠id顺序,初始为给定的顺序。
使用while循环,定义一个新的vecotr < int > cur 用来存放进入下一轮比较的老鼠的id,不断遍历ori数组,定义了一个priority_queue < mice > q,将k只老鼠加入q中,这样自动获得当前k只老鼠中体重最大的老鼠,也就知道了这k只老鼠中体重最大的老鼠的id,让该只老鼠的rcnt加1,并且将当前老鼠的id加入到cur中,再之后让将cur赋值给ori,开始下一轮循环,直到ori中只有一只老鼠为止。
再之后将mouse数组根据rcnt排序,依次给每只老鼠赋排名。
再之后将mouse数组根据id从小到大排,之后输出每只老鼠的排名即可。

#include <bits/stdc++.h>

using namespace std;

struct mice{
    int id;
    double weight;
    int rcnt,r;
    mice():rcnt(0){}

    friend bool operator < (const mice &a,const mice &b){
        return a.weight < b.weight;
    }
}mouse[1010];

bool cmprcnt(mice &a,mice &b){
    return a.rcnt > b.rcnt;
}

bool cmpr(mice &a,mice &b){
    return a.id < b.id;
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 0;i < n;i++) scanf("%lf",&mouse[i].weight);
    vector<int> ori;
    for(int i = 0;i < n;i++){
        int t;
        scanf("%d",&t);
        ori.push_back(t);
        mouse[i].id = i;
    }
    while(1){
        vector<int> cur;//定义在while里面,不然出问题
        for(int i = 0;i < ori.size(); ){//这里不要让i++
            int j = i;
            priority_queue<mice> q;//定义优先队列
            
            //找到k只老鼠,最后面不足k只,则到j==ori.size()结束,恰好满足条件
            //j要自增
            //注意是将id为ori[j]的老鼠加入到优先队列中
            //优先队列自动根据当前队列中的mice变量的体重进行调整,又快又自动
            while(j < ori.size() && j - i + 1 <= k) q.push(mouse[ori[j++]]);
            
            i = j;//令i = j
            mice temp = q.top();//取出当前组里面体重最大的老鼠
            int id = temp.id;//得到当前组老鼠中体重最大的老鼠的id
            mouse[id].rcnt++;//将该只老鼠的rcnt即轮数加1
            cur.push_back(id);//将该组胜者id加入到当前顺序数组cur中
        }
        if(cur.size() == 1) break;//如果cur中老鼠数量为1,即决出了最后的胜者,直接break
        ori = cur;//将ori赋为最新的一轮老鼠的id
    }

    sort(mouse,mouse + n,cmprcnt);//按照老鼠的轮数进行排名

    //给老鼠们赋排名
    int r = 1;
    for(int i = 0;i < n;i++){
        if(i && mouse[i].rcnt != mouse[i-1].rcnt) r = i + 1;
        mouse[i].r = r;
    }

    sort(mouse,mouse + n,cmpr);//按照老鼠的id从小到大进行排名

    for(int i = 0;i < n;i++){//输出每只老鼠对应的排名
        if(i) printf(" ");
        printf("%d",mouse[i].r);
    }

    return 0;
}

上一篇:划分训练集和测试集和验证集


下一篇:python获取知乎日报另存为txt文件