Codeforces Round #223 (Div. 2) B. Sereja and Stairs【模拟】

题意：已知n个数，要求构成一个数列，使得构成数列中一个数最大 ，往两边依次严格递减 ， 问这个数列最长多长并且输出该数列。

思路：最大的放中间，第二大的往两边放，以此类推。 实现过程：用map来计数，计数完成后复制给struct。这样的好处是可以节约很多不必要的空间消耗。然后开一个数组来模拟第一句话的思路。用left,right标记左边和右边的下标。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=1e5+50;
int ans[3*maxn];
map <int,int> mp;
struct node
{
    int v,cnt;
}d[maxn];

int main(void)
{
    int m;
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        mp[x]++;
    }
    int cnt=1;
    for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
        d[cnt].v=it->first, d[cnt].cnt=it->second,cnt++;
    //for(int i=1;i<cnt;i++)
    // printf("%d %d\n",d[i].v,d[i].cnt);
    int index=150000,left=150000,right=150000;
    ans[index]=d[cnt-1].v;
    left--,right++;
    for(int i=cnt-2;i>=1;i--)
    {
        if(d[i].cnt==1)
            ans[left--]=d[i].v;
        else if(d[i].cnt >=2)
            ans[left--]=ans[right++]=d[i].v;
    }
    printf("%d\n",(right-1)-(left+1)+1);
    for(int i=left+1;i<=right-1;i++)
        printf("%d ",ans[i]);
    printf("\n");
}