C - Heap Partition ZOJ - 3963

78 阅读 0 评论 52 点赞

我是靠谱客的博主明亮乌龟，最近开发中收集的这篇文章主要介绍C - Heap Partition ZOJ - 3963，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

C - Heap Partition

ZOJ - 3963

A sequence S = {s1, s2, ..., sn} is called heapable if there exists a binary tree Twith 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 < ihold. 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, ..., PiCiin 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

Sample Output

题目大意：

给定一个序列，要求通过这个序列构建最少数量的二叉树

树的要求是子节点 aj 的值要大于等于父亲节点 ai ，并且在序列中 aj 的下标 j 要大于 ai 的下标i

思路：

对于给定的序列，目的就是要在这个树中的最下一层，即子节点数量少于2的节点上添加对应要求的节点，我们可以通过一个set

来进行表示，并且，将这个set 进行从大到小排序，在这些能插入子节点的节点中，找到当前能够满足不大于插入节点 ai 的值的父节点即可。

代码：

#include<iostream>
#include<set>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
int T;
const int MAXN = 1e5+5;
int num[MAXN];
struct node{
	//对应的第几棵树，以及对应的下标 
	int first,second;
	
	// 可以通过这种方式实现，从小到大排列 
//	bool operator <(const node &b)const {
//		if(num[this->second]==num[b.second] ) return this->second< b.second;
//			return num[this->second] <num[b.second]; 
//	}
//	 
};
// 也可以通过这种方式实现，注意两者区别 
struct cmp{
	bool operator ()(const node &a,const node &b) {
		if(num[a.second]==num[b.second] ) return a.second< b.second;
			return num[a.second] <num[b.second]; 
	}
};
//对应存放树的序列 
vector<int> arr[MAXN];
//每个节点最多只能有两个子节点， 
int dig[MAXN];

//能够挂子节点的父亲节点 
set<node ,cmp> st;

int main(){
	
	scanf("%d",&T);
	node p;
	int count; 
	set<node>::iterator it;
	while(T--){
		int n;
		count =0;
		scanf("%d",&n);
		st.clear();
		memset(dig,0,sizeof(int)*(n+2));
		for(int i=1;i<=n;i++){
			scanf("%d",&num[i]);
			p.second = i;
			//找到第一个大于这个值得节点 
			it = st.upper_bound(p);
			
			//没有找到，说明目前这个节点最大，只能重新创建一颗树 
			if(it == st.begin()){
				p.first = count; p.second = i;
				st.insert(p);
				arr[count].push_back(i);
			 	count++;
			}else{
			
				it--;
				//找到不大于这个节点的最大值 
				p = *it;
				
				//给父节点接上子节点 
				dig[p.second]++;
				//不能再接了，从中删除 
				if(dig[p.second]>=2) st.erase(it);
				p.second = i;
				arr[p.first].push_back(i);
				st.insert(p);
			}
		}
		
		printf("%dn",count);
		for(int i=0;i<count;i++){
			printf("%d",arr[i].size());
			for(int j=0;j<arr[i].size();j++){
				printf(" %d",arr[i][j]);
			}
			printf("n");
			arr[i].clear();
		}
//		printf("n");
	}
	
	return 0;
}