ZOJ 3963 Heap Partition (STL)

95 阅读 0 评论 63 点赞

我是靠谱客的博主迅速紫菜，最近开发中收集的这篇文章主要介绍ZOJ 3963 Heap Partition (STL)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Heap Partition

Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge

A sequence S = {s1, s2, …, sn} is called heapable if there exists a binary tree T with n nodes 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

题意：序列 S={s1,s2,…,sn} 被称为 heapable ，当且仅当存在一个二叉树 T ， n 个点均作为 T 的一个节点，且满足任意非根节点 si 和其父节点 sj , sj≤si 且 j< i 。现在有一个序列 a1,a2,…,an ，相应将其分成若干个 heapable 的子序列，问使得子序列个数最少的策略。
题解：对于每一个新插入的点，找前面≤它的最大点做为它的父亲。没有就新建一个。注意一点节点可以有两个儿子。
代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
#include<string.h>
#define ll long long
using namespace std;
const int N=1e5+10;
struct node
{
    int v,d,id;
    node(int v,int d,int id):v(v),d(d),id(id){}
    bool operator <(const node &t)const
    {
        return v<t.v;
    }
};
multiset<node>s;
multiset<node>::iterator it;
vector<int>g[N];
int main()
{

    int t,n,x;
    scanf("%d",&t);
    while(t--)
    {
        s.clear();
        int id=0;
        scanf("%d%d",&n,&x);
        for(int i=1;i<=n;i++) g[i].clear();
        s.insert(node(x,0,++id));
        g[id].push_back(1);
        for(int i=2;i<=n;i++)
        {
          scanf("%d",&x);
          it=s.upper_bound(node(x,0,0));
          if(it==s.begin())
          {
              s.insert(node(x,0,++id));
              g[id].push_back(i);
          }
          else
          {
              node v=*(--it);
              s.erase(it);
              s.insert(node(x,0,v.id));
              g[v.id].push_back(i);
              if(v.d==0)
                s.insert(node(v.v,1,v.id));
          }
        }
        printf("%dn",id);
        for(int i=1;i<=id;i++)
        {
            printf("%d",g[i].size());
            for(int j=0;j<g[i].size();j++)
                printf(" %d",g[i][j]);
            printf("n");
        }
    }
}