PAT (Advanced Level) Practice 1109 Group Photo (25 分) 凌宸1642

2023-12-21 15:49:52

PAT (Advanced Level) Practice 1109 Group Photo (25 分) 凌宸1642

题目描述：

Formation is very important when taking a group photo. Given the rules of forming K rows with N people as the following:

The number of people in each row must be N/K (round down to the nearest integer), with all the extra people (if any) standing in the last row;
All the people in the rear row must be no shorter than anyone standing in the front rows;
In each row, the tallest one stands at the central position (which is defined to be the position (m/2+1), where m is the total number of people in that row, and the division result must be rounded down to the nearest integer);
In each row, other people must enter the row in non-increasing order of their heights, alternately taking their positions first to the right and then to the left of the tallest one (For example, given five people with their heights 190, 188, 186, 175, and 170, the final formation would be 175, 188, 190, 186, and 170. Here we assume that you are facing the group so your left-hand side is the right-hand side of the one at the central position.);
When there are many people having the same height, they must be ordered in alphabetical (increasing) order of their names, and it is guaranteed that there is no duplication of names.

Now given the information of a group of people, you are supposed to write a program to output their formation.

译：合影时，阵型很重要。给定 N 人形成 K 行的规则如下：

每行的人数必须是 N/K（向下取整到最接近的整数），所有额外的人（如果有）都站在最后一行；
所有后排的人不得比站在前排的任何人矮；
在每一行中，最高的站在中心位置（定义为位置（m/2+1），其中m为该行的总人数，除法结果必须四舍五入为最接近的整数）；
在每一行中，其他人必须按照他们的身高不增加的顺序进入该行，轮流在最高的人的右边和左边占据他们的位置（例如，给定五个人的身高 190、188、 186、175 和 170，最终的阵型将是 175、188、190、186 和 170。这里我们假设您面向该组，因此您的左侧是*组的右侧位置。）;
当有很多人身高相同时，必须按照姓名的字母（递增）顺序排列，并保证不出现重复姓名。

现在给定一组人的信息，你应该编写一个程序来输出他们的阵型。

Input Specification (输入说明):

Each input file contains one test case. For each test case, the first line contains two positive integers N (≤ 10⁴ ), the total number of people, and K (≤10), the total number of rows. Then N lines follow, each gives the name of a person (no more than 8 English letters without space) and his/her height (an integer in [30, 300]).

译：每个输入文件包含一个测试用例。对于每个测试用例，第一行包含两个正整数 N（≤ 10⁴ ），总人数和 K（≤10），总行数。然后是N行，每行给出一个人的名字（不超过8个英文字母，不含空格）和他/她的身高（[30, 300]中的整数）。

output Specification (输出说明):

For each case, print the formation -- that is, print the names of people in K lines. The names must be separated by exactly one space, but there must be no extra space at the end of each line. Note: since you are facing the group, people in the rear rows must be printed above the people in the front rows.

译：对于每种情况，打印队形——即在 K 行中打印人名。名称必须正好由一个空格分隔，但每行末尾不得有多余的空格。注意：因为你是面对人群，所以后排的人必须打印在前排的人上方。

Sample Input (样例输入):

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

Sample Output (样例输出):

Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John

The Idea：

对输入的数据进行排序，按照身高为第一依据，然后身高相同时，名字的字典序为第二依据。
根据输入的人数 n 和行数 k ，可以确定每行有多少人(最后一行比较特殊)。
从最后一行开始，按照要求排序，先拍最高人的位置，然后根据最高人先右再左(我们的先左再右) 依次轮流左右编排。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 10010 ;
struct Peo{
	string name ;
	int height ;
}peo[maxn] ;
int n , k , col , last  ; 
vector<vector<string> > ans ;
bool cmp(Peo a , Peo b){
	if(a.height != b.height) return a.height < b.height ;
	return a.name > b.name ;
}
int main(){
	cin >> n >> k ;
	for(int i = 0 ; i < n ; i ++) cin >> peo[i].name >> peo[i].height ;
	sort(peo , peo + n , cmp) ;
	col = n / k , last = col + n % k ;  // n / k 自动向下取整得到每行人数，最后一行在此基础上加上 n 对 k 的取余的余数
	vector<string> temp(last) ;
	int mid = last / 2 , i = n - 1 ;
	temp[mid] = peo[i --].name ;  // 最后一排最高人位置
	for(int j = 1 ; j < last ; j ++ , i -- ){
		if(j % 2) temp[mid - j/2 - 1] = peo[i].name ;
		else temp[mid + j/2] = peo[i].name ;	
	}
	ans.push_back(temp) ;
	mid = col / 2 ;
	for(int j = 1 ; j < k ; j ++ ){
		vector<string> te(col) ;
		te[mid] = peo[i --].name ;  // 剩下的每行最高人的位置
		for(int s = 1 ; s < col ; s ++ , i -- ){
			if(s % 2) te[mid - s/2 - 1] = peo[i].name ;
			else te[mid + s/2] = peo[i].name ;	
		}
		ans.push_back(te) ;    
	}
	for(int i = 0 ; i < k ; i ++){
		for(int j = 0 ; j < ans[i].size() ; j ++){
			cout << ans[i][j] << ((j == ans[i].size() - 1)?'\n':' ') ;
		}
	}
	return 0 ;
}

码农公寓