Heap Partition ZOJ - 3963

A sequence S = {s1, s2, ..., sn} is called heapable if there exists a binary tree T with nnodes such that every node is labelled with exactly one element from the sequence S, and for every non-root node si and its parent sj, sj ≤ si and j < i hold. Each element in sequence S can be used to label a node in tree T only once.

Chiaki has a sequence a1, a2, ..., an, she would like to decompose it into a minimum number of heapable subsequences.

Note that a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contain an integer n (1 ≤ n ≤ 105) — the length of the sequence.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n).

It is guaranteed that the sum of all n does not exceed 2 × 106.

Output

For each test case, output an integer m denoting the minimum number of heapable subsequences in the first line. For the next m lines, first output an integer Ci, indicating the length of the subsequence. Then output Ci integers Pi1, Pi2, ..., PiCi in increasing order on the same line, where Pij means the index of the j-th element of the i-th subsequence in the original sequence.

Sample Input

4
4
1 2 3 4
4
2 4 3 1
4
1 1 1 1
5
3 2 1 4 1

Sample Output

1
4 1 2 3 4
2
3 1 2 3
1 4
1
4 1 2 3 4
3
2 1 4
1 2
2 3 5

思路：set记录并更新每个树的最大值   vector记录每个树的路径 。对set进行二分（找最后一个符合条件的值）找到要更新的树，并更新set和vector。      
此外 注意 一个节点有两个儿子，当都找到这两个儿子时才删除set中的父亲节点

#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
#include <algorithm>
#include<iostream>
#include<set>
#include<map>
#include<vector>
using namespace std;
struct node{//重新定义set
    int cnt,num,d;
    node (int cnt,int num,int d):cnt(cnt),num(num),d(d){}
    bool operator <(const node &t)const{
        return num<t.num;
    }
};
int a[100861];
vector<int>mp[100861];
multiset<node>s;
multiset<node>::iterator it;
int main(){
    int t,n,cnt=1;
    cin>>t;
    while(t--){
        cnt=1;
        //cin>>n;
        scanf("%d",&n);
        s.clear();
        for(int i=0;i<n;i++)mp[i].clear();
        for(int i=0;i<n;i++){
            //cin>>a[i];
            scanf("%d",&a[i]);
        }
        mp[cnt].push_back(1);
        s.insert({1,a[0],0});
        for(int i=1;i<n;i++){
            it=s.upper_bound({0,a[i],0});
            if(it==s.begin()){
                cnt++;
                s.insert({cnt,a[i],0});
                mp[cnt].push_back(i+1);
            }
            else{
                node q=*(--it);
                s.erase(it);
                s.insert({q.cnt,a[i],0});
                mp[q.cnt].push_back(i+1);
                if(!q.d){//只有一个儿子时
                    s.insert({q.cnt,q.num,1});
                }
            }
        }
        printf("%dn",cnt);
        for(int i=1;i<=cnt;i++){
            printf("%d",mp[i].size());
            for(int j=0;j<mp[i].size();j++){
                printf(" %d",mp[i][j]);
            }
            printf("n");
        }

    }
    return 0;
}

最后

以上就是机灵饼干为你收集整理的Heap Partition ZOJ - 3963的全部内容，希望文章能够帮你解决Heap Partition ZOJ - 3963所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。