Offer收割

1.水题

2.BFS宽搜（使用优先队列priority_queue）

4.题意：给数组a。要求重排列数组，使得数组中的任意相邻的两个元素不同。如果存在多个方案，那么选择字典序最小的方案。

　　　如果不能满足如上要求，输出“-1”。

思路：使用贪心策略。每次如果剩下的元素刚好达到可以分割当前Num[i]的数目下限个元素的时候，那么此时就必须安排num[i];

　　否则，安排最小的元素。且和上一个元素不同。

使用map来统计数值出现的个数，使用set<pair, pair>来记录map中的<second, first> <=> <cnt, num>。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <string.h>

#include <set>

#include <map>

using namespace std;

const int Maxn = ;

int n, a[Maxn];

map<int, int>cnt;

set<pair<int, int>>S;

int main()

{

    cin>>n;

    for(int i = ; i < n; i ++){

        scanf("%d",&a[i]);

        cnt[a[i]] ++;

    }

    map<int, int>::iterator it;

    for(it = cnt.begin(); it != cnt.end(); it ++){

        S.insert(make_pair(it->second, it->first));

    }

    if((--S.end())->first *  -  > n){

        cout<<"-1"<<endl;

        return ;

    }

    int pre_x = -;

    for(int i = ; i <= n; i ++){

        int x;

        if((--S.end())->first *  -  == (n + i - )){

            x = (--S.end())->second;

        }else{

            it = cnt.begin();

            while(it->first == pre_x && it != cnt.end()){

                it ++;

            }

            x = it->first;

        }

        S.erase(make_pair(cnt[x], x));

        cnt[x] --;

        if(cnt[x] > ){

            S.insert(make_pair(cnt[x], x));

        }else{

            cnt.erase(x);

        }

        printf("%d%c",x, i == n?'\n':' ');

        pre_x = x;

    }

    return ;

}

巴特西

Offer收割_4

最新文章

热门文章