PTA basic 1055 集体照 (25 分) c++语言实现(g++)

2021/5/9 20:27:30

本文主要是介绍PTA basic 1055 集体照 (25 分) c++语言实现(g++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

拍集体照时队形很重要,这里对给定的 N 个人 K 排的队形设计排队规则如下:

  • 每排人数为 N/K(向下取整),多出来的人全部站在最后一排;

  • 后排所有人的个子都不比前排任何人矮;

  • 每排中最高者站中间(中间位置为 m/2+1,其中 m 为该排人数,除法向下取整);

  • 每排其他人以中间人为轴,按身高非增序,先右后左交替入队站在中间人的两侧(例如5人身高为190、188、186、175、170,则队形为175、188、190、186、170。这里假设你面对拍照者,所以你的左边是中间人的右边);

  • 若多人身高相同,则按名字的字典序升序排列。这里保证无重名。

现给定一组拍照人,请编写程序输出他们的队形。

输入格式:

每个输入包含 1 个测试用例。每个测试用例第 1 行给出两个正整数 N(≤10​4​​,总人数)和 K(≤10,总排数)。随后 N 行,每行给出一个人的名字(不包含空格、长度不超过 8 个英文字母)和身高([30, 300] 区间内的整数)。

输出格式:

输出拍照的队形。即K排人名,其间以空格分隔,行末不得有多余空格。注意:假设你面对拍照者,后排的人输出在上方,前排输出在下方。

输入样例:

10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
 

输出样例:

Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John

 

测试点3 4 5的测试用例

10 10
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159

解题思路

1.题目本身就是分割子序列然后按照特定规则重排序的过程,因此 需要将代码分为两部分,一个是分割子序列, 一个是重排序的过程

2.分割子序列按照题目要求,分为k排,最多10排, 前 k-1 排有 row=n/k; 个元素   最后一排lastRow有 row+n%k;个元素,

3.按照身高姓名排序时,  如果按照从小到大顺序排列,  身高不同时身高更高的人在后,  身高相同时,名字字母序小的在后

4.按题目说明,  输出排列的时候 和 毕业照 的形式一致,   最先输出的是最后一排, 最后输出的是第一排

  题目要求每一排中,最高的人在中间位置,然后按照先右后左的顺序依次放入次高,  这里的左右是照片中最高的人面向镜头时的左和右,在输出的时候是镜像的

  因此每一排在重新排序的时候,应该是按照 以最高的人为界,先左后右的顺序依次放入次高的人

4.按照最后一排到第一排的顺序 依次输出

 

 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class student {
public:
    string name;
    int tall;
    student()=default;
    student(string name_,int tall_):name{name_},tall{tall_}{};
};
void reOrder(vector<student>&templist){//按照要求,把最高的放 行中间,然后按照先右后左的顺序依次放入次高的
    int size=templist.size();
    vector<student> temp(size);
    int mid=size/2,left{mid-1},right={mid+1},count{1};
    temp[mid]=templist[0];
    while(count!=size){
        if(count%2){
            if(left>=0){
                temp[left--]=templist[count++];
            }else if(right<size){
                temp[right++]=templist[count++];
            }

        }else{
            if(right<size){
                temp[right++]=templist[count++];
            }else if(left>=0){
                temp[left--]=templist[count++];
            }
        }
    }
    templist=temp;
}

bool compare(student l,student r){//快排的比较规则,身高大的 或者 字母序小的 元素 是 大元素, 小元素在前,大元素靠后
    bool flag=0;
    if(l.tall!=r.tall){//身高不同时
        flag=l.tall<r.tall;//左边身高 小于 右边时,右边的是大元素
    }else{//同身高比较name字符串
        flag=l.name.compare(r.name)>0;// l.name字符串 逐个跟 r.name字符串比较,
        //string.compare(argument)的返回值, string字符大于参数argument的字符时,返回1,小于返回-1,等于返回0
        //如果l的字符 大于 r的字符 , 既返回值为1时,   右边是小字母,右边是大元素
    }
    return flag;
}
int main(){
    int n,k,tempTall;
    int row,lastRow;
    string tempName;
    vector<vector<student>> list;
    vector<student>tempList;
    vector<student>tempRow;
    cin >> n>> k;
    if(k>10)k=10;//排数,最多10排
    row=n/k;//除最后一排外,每排站多少人
    lastRow=row+n%k;//剩下的人数
    
    for(int i=0;i<n;i++){
        cin >> tempName >> tempTall;
        student tempStudent{tempName,tempTall};
        tempList.push_back(tempStudent);
    }
    
    //按身高从小到大排序,同身高的按名字的字母从大到小排序
    sort(tempList.begin(),tempList.end(),compare);
    
    //拆分成多排,先把最后一排的元素 加入到二维数组中
    for(int i=0;i<lastRow;i++){
        tempRow.push_back(tempList.back());
        tempList.pop_back();
    }
    list.push_back(tempRow);
    tempRow.clear();
    for(int i=k-2;i>=0;i--){//再把剩下的每一排,按照从 倒数第二排 到 第一排 的顺序加入到二维数组中
        for(int j=row-1;j>=0;j--){
            tempRow.push_back(tempList[i*row+j]);
        }
        list.push_back(tempRow);
        tempRow.clear();
    }
    
    //每一排都重排序
    for(int i=0;i<list.size();i++){
        reOrder(list[i]);
    }
    
    //按序输出
    for(int i=0;i<list.size();i++){
        int j;
        for(j=0;j<list[i].size()-1;j++){
            cout << list[i][j].name<<" ";
        }
        cout <<list[i][j].name<<endl;//每一排末尾单独输出
    }
    return 0;
}

 



这篇关于PTA basic 1055 集体照 (25 分) c++语言实现(g++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程