1055 集体照 较复杂

关键

1. 双端队列的使用
2. 数值和字符串的相互映射（有重复值）

代码

#include <iostream>
#include <cstdio>
#include <string>
#include <set>
#include <deque>
#include <algorithm>
using namespace std;

string array[300][2000];
int a[10001];
string h[10001];
string h2[10001];

int main(){

	int n,k;
	int count;
	string name;
	int height;
	multiset<int> st;
	deque<string> dq;
	int tmp3;
	int tmp4=0;
	cin>>n>>k;
	count=n/k;//最后一排: n-count*(k-1)
	for(int i=0;i<n;i++){
		cin>>name>>height;
		tmp3=0;
		while(array[height][tmp3]!=""){
			tmp3++;
		}
		array[height][tmp3]=name;
		for(int j=tmp3;j>=0;j--){
			h[j]=array[height][j];
		}
		sort(h,h+tmp3+1); 
		for(int j=tmp3;j>=0;j--){
			array[height][j]=h[j];
		}
		st.insert(height);
	}
	int tmp=0;
	for(multiset<int>::iterator it=st.begin();it!=st.end();it++){//按身高有序排列 
		a[tmp]=*it;
		while(array[a[tmp]][tmp4]!=""){
			tmp4++;
		}
		h2[tmp]=array[a[tmp]][tmp4-1];
		array[a[tmp]][tmp4-1]="";
		tmp4=0;
		tmp++;
	}

	
	int tmp2;
	for(int i=0;i<k-1;i++){
		tmp2=0;
		for(int j=count-1;j>=0;j--){
			if(tmp2%2==0){
				dq.push_back(h2[i*count+j]);
			}
			else{
				dq.push_front(h2[i*count+j]);
			}
			tmp2++;
		}
		for(int j=0;j<count;j++){
			h2[i*count+j]=dq.front();
			dq.pop_front();
		}
	}
	tmp2=0;
	for(int i=n-1;i>=count*(k-1);i--){	
		if(tmp2%2==0){
			dq.push_back(h2[i]);
		}
		else{
			dq.push_front(h2[i]);
		}
		tmp2++;
	}
	for(int i=count*(k-1);i<n;i++){	
		h2[i]=dq.front();
		dq.pop_front();
	}


	for(int i=count*(k-1);i<=n-1;i++){
		if(i==count*(k-1)){
			cout<<h2[i];
		}
		else{
			cout<<" "<<h2[i];
		}
	}
	cout<<endl;

	for(int i=k-2;i>=0;i--){
		for(int j=0;j<=count-1;j++){
			if(j==0){
				cout<<h2[i*count+j];
			}
			else{
				cout<<" "<<h2[i*count+j];
			}
		}
		if(i!=0){
			cout<<endl;
		}
	}
    return 0;
}