[HDU] 2611 Sequence two 优先队列和一般队列一起使用。

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2611

方法：

和hdu 2610不一样，该题中要求的顺序除了根据长度外是根据数字大小而不是数字所在的下标，所以不像2610那样有现成的顺序在那里我们只需要去扫描就可以了，所以这里要使用优先队列，但如果对所有的状态都用优先队列来放的话，这会带来很大的时间开销所以，本程序的处理是，

　　1，将当前已经探寻到了状态维护在一个一般队列中，并且保证其入队出队顺序和题目要求一致。

　　2，当出来一个状态，准备去探索一堆新状态的时候，由于都是同一个状态探寻到的，所以它们携带的数组长度一样，所以这里只需要对大小排序。在由于都是同一个状态探寻到的，所以这些新状态携带的数组就只有最后一个不一样，对大小排序其实就是对最后一个数排序，于是这里先用根绝最后一个数排序的优先队列将其全部压入，然后再一个一个弹出到一般队列，这样就再一次保证了一般队列中的顺序和题目要求一致。

　　3.由于不再是根据下标来排序，所以当探寻到的状态节点个数超过要求的输出个数时还要继续探寻，因为在前面探寻到的有可能根据大小排序后就根本不会输出了，后面没有被探寻到的有可能比较小反而可以输出。这个一个让我wa了很久的地方。

感想：该算法虽然ac了，但后面还是要用数学归纳法去证明其正确性。

代码：

#include <iostream>
#include <queue>
#include <map>
#include<algorithm>
using namespace std;
int n,p;
int numbers[101];
int t_numbers[101];
bool visisted[101];
int* arrays[200005];
struct Nums
{
    int count;
    int numbersNo;
    int end;
};
int t_n;
struct cmp
{
    bool operator()(Nums x,Nums y)
    {
        if(x.count>y.count)
            return true;
        if(x.count==y.count && numbers[x.end]>numbers[y.end])
            return true;
        return false;
        
    }
};
void  BFSearch(map <int,int>::iterator iter,map <int,int> mp)
{
     queue<Nums> q;
     int curr=0;
     int i =0;
      priority_queue<Nums,vector<Nums>,cmp> pq2;
     for(i=0;i<n;i++)
     {
         iter = mp.find(numbers[i]);
         if(!visisted[ iter->second])
         {
            Nums nums;
            nums.count=1;
            nums.end=i;
            nums.numbersNo=i;
            arrays[    nums.numbersNo] =new int[1];
            arrays[    nums.numbersNo][0] = numbers[i];
            visisted[iter->second] = true;
            pq2.push(nums);
         }
     }
      while(!pq2.empty())
         {
             q.push(pq2.top());
             pq2.pop();
         }
     curr = i;
     int count =0;
     while(!q.empty() && count<p)
     {
         memset(visisted,false,sizeof(visisted));
         Nums t_nums = q.front();
         q.pop();
         count++;
         for(int j=0;j<t_nums.count-1;j++)
         {
             printf("%d ",arrays[t_nums.numbersNo][j]);
         }
         printf("%d\n",arrays[t_nums.numbersNo][t_nums.count-1]);
              
         Nums n_nums;
         priority_queue<Nums,vector<Nums>,cmp> pq;
         for(int j=t_nums.end+1;j<n;j++)
         {
             
             iter = mp.find(numbers[j]);
             if(numbers[j]>=numbers[t_nums.end] && !visisted[iter->second] && curr<=200005)
             {
                 visisted[iter->second] = true;
                 n_nums.count = t_nums.count+1;
                 n_nums.end = j;
                 n_nums.numbersNo = curr;
                 arrays[n_nums.numbersNo] = new int[n_nums.count];
                 int x=0;
                 for(x=0;x<t_nums.count;x++)
                    arrays[n_nums.numbersNo][x] = arrays[t_nums.numbersNo][x];
                arrays[n_nums.numbersNo][x]=numbers[j];
                pq.push(n_nums);
                curr++;
             }
         }
         while(!pq.empty())
         {
             q.push(pq.top());
             pq.pop();
         }
         delete[]  arrays[t_nums.numbersNo];
     }
}
void map_insert(map < int, int > *mapStudent, int o, int x) 
{ 
    mapStudent->insert(map < int, int >::value_type(o, x)); 
} 

void main()
{
    while(scanf("%d %d",&n,&p)!=EOF)
    {
        map <int,int>::iterator iter;
        map <int,int> mp;
        memset(numbers,0,sizeof(numbers));
        memset(visisted,false,sizeof(visisted));
        int k =0;
        t_n=n;
        for(int i =0;i<n;i++)
        {
            scanf("%d",&numbers[i]);
            iter = mp.find(numbers[i]);
            if(iter ==mp.end())
            {
                map_insert(&mp,numbers[i],k);
                k++;
            }
        }
         BFSearch(iter,mp);
        printf("\n");
    }
}