当前位置: 代码迷 >> 综合 >> PAT乙级-1055 集体照 (25分)
  详细解决方案

PAT乙级-1055 集体照 (25分)

热度:78   发布时间:2023-09-27 00:48:40.0

点击链接PAT乙级-AC全解汇总

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

  • 每排人数为 N/K(向下取整),多出来的人全部站在最后一排;
  • 后排所有人的个子都不比前排任何人矮;
  • 每排中最高者站中间(中间位置为 m/2+1,其中 m 为该排人数,除法向下取整);
  • 每排其他人以中间人为轴,按身高非增序,先右后左交替入队站在中间人的两侧(例如5人身高为190、188、186、175、170,则队形为175、188、190、186、170。这里假设你面对拍照者,所以你的左边是中间人的右边);
  • 若多人身高相同,则按名字的字典序升序排列。这里保证无重名。

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

输入格式:
每个输入包含 1 个测试用例。每个测试用例第 1 行给出两个正整数 N(≤104?? ,总人数)和 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

我的代码:

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
#include<sstream>
using namespace std;
//有的时候题目是一起做的,所以会有不需要的头文件int cmp(pair<string,int>a,pair<string,int>b){
    if(a.second!=b.second)   return a.second>b.second;else return a.first<b.first;
}void print_first_to_last(pair<string,int>student[],int first,int last)
{
    int m=last-first+1;int first_=(m%2==0)?(last):(last-1);int end_=(m%2==0)?(last-1):(last);int i=first_;while(i>=first+1){
    cout<<student[i].first<<" ";i-=2;}i=first;while(1){
    cout<<student[i].first;i+=2;if(i<=end_) cout<<" ";else{
    cout<<endl;return;}}
}int main()
{
    int N,K;cin>>N>>K;pair<string,int>student[N];for(int i=0;i<N;i++){
    string name;int height;cin>>name>>height;student[i]=make_pair(name,height);}sort(student,student+N,cmp);int num_line=N/K;print_first_to_last(student,0,num_line+N%K-1);for(int line=2;line<=K;line++)print_first_to_last(student, N%K+(line-1)*num_line, N%K + line*num_line -1);return 0;
}

我的思路:

确定每一行的范围:一共N个人,除了第一行,有K行

  1. 第一行有N/K+N%K

    下标从0 ~ N/K+N%K-1

  2. 那么2 ~ K行每行有N/K

    对于第line行,
    第一个下标是N/K + N%K + (line-2)*N/K = N%K + (line-1)*N/K
    最后一个下标N%K + (line-1)*N/K + N/K-1 = N%K + line*N/K -1

对于某一行的输出:对下标排序,然后按照下标的顺序挨个输出就好了

  1. 按照身高排序,下标对应0 ~ N-1
  2. 对于某一行 比如说m个 那么有两种情况
  • m是偶数: (m-1)…3 1 0 2 4…(m-2)

    • 第一个是:最后一个
    • 中间停在:1(第一个的后一个)
    • 最后一个是:最后一个前一个
  • m是奇数: (m-2)…3 1 0 2 4…(m-3) (m-1)

    • 第一个是:最后一个前一个
    • 中间停在:1(第一个的后一个)
    • 最后一个是:最后一个
  1. 对于每一行,第一个为下标first,最后一个下标lastm=last-first+1
  • m是偶数: 从 last -2 -2 到first+1 ,再从first +2 +2到 last-1
  • m是奇数: 从 last-1 -2 -2 到first+1 ,再从first +2 +2到 last
  相关解决方案