PAT (Advanced Level) 1109. Group Photo (25)

简单模拟。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;

struct X
{
    string name;
    int h;
} s[100000+10];
int n,k;
vector<int>g[200];
int tmp[10000+10];

bool cmp(const X&a,const X&b)
{
    if(a.h==b.h) return a.name<b.name;
    return a.h>b.h;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        cin>>s[i].name>>s[i].h;
    sort(s+1,s+n+1,cmp);

    int t=n+1;
    for(int i=k; i>=1; i--)
    {
        int m;
        if(i>1) m=n/k;
        else m=n-n/k*(k-1);
        t=t-m;
        int y=t,p=m/2+1,sz=0;
        int L,R;
        tmp[p]=y++,sz++,L=p-1,R=p+1;
        while(1)
        {
            if(sz==m) break;
            if(sz%2==0) tmp[R++]=y++;
            else tmp[L--]=y++;
            sz++;
        }
        for(int j=1;j<=m;j++) g[i].push_back(tmp[j]);

    }
    for(int i=1; i<=k; i++)
    {
        for(int j=0; j<g[i].size(); j++)
        {
            cout<<s[g[i][j]].name;
            if(j<g[i].size()-1) printf(" ");
            else printf("
");
        }
    }
    return 0;
}