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

C++ - PAT - 1055. 集体照 (25)

热度:105   发布时间:2023-10-09 19:02:58.0

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

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

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

输入格式:

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

思路:先将所有人按照身高递增排序。根据题意可知,中间的人的身高是最高的,然后次高的在左边,再低的右边,依此类推。可以想到用Deque中的push_back()和push_front();也可以用string的相加拼接。这里用了后者。


#include<iostream>
#include<algorithm>
#include<string>
using namespace std;int n,k;
int last,ave;
string ans="";
struct P{string name;int heigh;
};bool cmp(P p1,P p2){	//身高从小到大 名字字典序从大到小 if(p1.heigh!=p2.heigh){return p1.heigh<p2.heigh;}else{return p1.name>p2.name;}}int main(){scanf("%d%d",&n,&k);P p[n];for(int i=0 ;i<n ;i++){cin>>p[i].name>>p[i].heigh;}sort(p,p+n,cmp);ave = n/k;	//行 string line = "";	string kk = " ";for(int i=0 ;i<k;i++){int begin = i*ave;	 int end = i*ave+ave-1;if(end+ave>=n){	//剩下的人不够再一行,end = n-1;	//补到这一行  }line = p[end].name;	//中间最大 for(int j=end-1 ;j>=begin ;j--){	//从大到小排列 if(j%2!=end%2){		 line = p[j].name+kk+line;	//左边 }else{		line = line+kk+p[j].name;	//右边 }}ans = line+"\n"+ans;}cout<<ans;return 0;
} 


  相关解决方案