PAT甲级1109 Group Photo

梦里梦外; 2023-03-12 10:51 18阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
**思路：**  
1. 结构体p存储学生姓名和身高信息，自定义cmp排序规则是按身高递减序，如果身高一样则按名字字典序升序  
 2.getorder函数实现将num个人按照cmp规则排序好后，将其在一排中的位置记录好  
**举个例子：这里有五个人，排序好后是1、2、3、4、5，他们在一排中的位置应该为4、2、1、3、5**  
3.human数组存储当前排的人信息，order数组存储位置信息，遍历每一排，更新两个数组信息，然后调用output函数输出结果

#include<iostream>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    struct p{ 
      int height;
      string name;
    };
    bool cmp(p a,p b)
    { 
      if(a.height!=b.height)return a.height>b.height;
      else return a.name<b.name; 
    }
    void getorder(vector<int> &v,int num)
    { 
    	int temp=num;
    	if(num%2==0)
    	{ 
    		while(temp>1)
    		{ 
    			v.push_back(temp);
    			temp-=2;
    		}
    		for(int i=1;i<num;i+=2)
    		{ 
    			v.push_back(i);
    		}
    	} 
    	else
    	{ 
    		temp--;
    		while(temp>1)
    		{ 
    			v.push_back(temp);
    			temp-=2;
    		}
    		for(int i=1;i<=num;i+=2)
    		{ 
    			v.push_back(i);
    		}
    	}
    }
    void output(vector<p> a,vector<int> b)
    { 
    	cout<<a[b[0]-1].name;
    	for(int i=1;i<b.size();i++)
    	{ 
    		cout<<" "<<a[b[i]-1].name;
    	}
    	cout<<endl;
    } 
    int main()
    { 
      int n,k;
      cin>>n>>k;
      vector<p> v;
      for(int i=0;i<n;i++)
      { 
        p it;
        cin>>it.name>>it.height;
        v.push_back(it);
      }
      sort(v.begin(),v.end(),cmp);
      //输出最后一排
      vector<p> human;
      vector<int> order;
      getorder(order,n-(k-1)*(n/k));
      int i;
      for(i=0;i<n-(k-1)*(n/k);i++)
      { 
      	human.push_back(v[i]);
      }
      output(human,order);
      order.clear();
      //输出剩下的k-1排
      getorder(order,n/k);
      for(int j=i;j<n;j+=n/k)
      { 
      	human.clear();
      	for(int x=0;x<n/k;x++)human.push_back(v[j+x]);
      	output(human,order);
      }
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230312/c2a2fe00a7484a10932436623ba9df98.png