相同数字距离大于minDis

一亩三分地

题目要求如下：输入： List，int minDistance 要求：输出任意permutation使得List中的相同element的间距要小于minDistance。

例1： 输入：[B, E, A, C, D, F, F]，2 输出：[B, F, A, C, D, E, F]

例2： 输入：[A, B, B]，1 输出：[A, B, B]

例3： 输入：[A, B, B]，2
输出：[B, A, B].

• 用一个heap维护当前出现次数的那些元素，出现次数最大在最前。
• 每次循环知道满足可以push下一个相同元素要求后再进入下一次循环
• 本次循环结束把更新的字符串和数字重新压入优先级队列。

struct Node
{
    string str;
    int times;
    Node(string _str,int _times)
    {
        str=_str;
        times=_times;
    }
};

struct Compare
{
    bool operator()(Node &n1,Node &n2)
    {
        return n1.times<n2.times;
    }
};

vector<string> reorder(vector<string> &strs,int dis)
{
    map<string,int> m;
    for(int i=0;i<strs.size();i++)
    m[strs[i]]++;

    priority_queue<Node,vector<Node>,Compare> pq;

    for(map<string,int>::iterator it=m.begin();it!=m.end();it++)
    {
        pq.push(Node(it->first,it->second));
    }

    vector<string> ret;

    while(!pq.empty())
    {
        vector<Node> tmp;

        int i=0;
        while(i<dis && !pq.empty())
        {
            Node node=pq.top();
            pq.pop();
            ret.push_back(node.str);
            if(node.times>1)
            {
                node.times--;
                tmp.push_back(node);
            }
        }

        for(int i=0;i<tmp.size();i++)
        {
            pq.push(tmp[i]);
        }
    }

    return ret;
}