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

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

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

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

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

输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出两个正整数 N（≤10⁴ ，总人数）和 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
1
2
3
4
5
6
7
8
9
10
11

输出样例：

Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John
1
2
3

我的代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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;
}

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

我的思路：

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

第一行有N/K+N%K人

下标从0 ~ N/K+N%K-1
那么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

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

按照身高排序，下标对应0 ~ N-1
对于某一行比如说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（第一个的后一个）
- 最后一个是：最后一个

对于每一行，第一个为下标first，最后一个下标last，m=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

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

评论记录：