Heap PartitionTime 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
Hint
d.构造尽可能少的二叉树结构，孩子节点要大于父节点，
比如样例2中，最少可构造2个，分别是2 4 3和1
输出的是数字在原序列中的位置
s.前面的数字从小到大排序，贪心选择尽可能大的构造
如果找不到比当前数字小的，则当前数字作为根，添加一个堆
样例较大，用set来写，二分查找比较快
1 #include
2 using namespace std;
3
4 const int MAXN = 1e5 + 5;
5
6 struct Node {
7 int id;
8 int val;
9 } a[MAXN];
10
11 int fa[MAXN];
12 int childNum[MAXN];//
13
14 struct NodeCmp {
15 bool operator()(const Node &a, const Node &b)
16 {
17 if (a.val != b.val) return a.val < b.val;
18 return a.id < b.id;
19 }
20 };
21
22 set
23 vector
24 vector
25
26 int setFind(int d)
27 {
28 if (fa[d] < 0) {
29 return d;
30 }
31 return fa[d] = setFind(fa[d]);
32 }
33
34 void setJoin(int x, int y)
35 {
36 x = setFind(x);
37 y = setFind(y);
38 if (x != y) fa[x] = y;
39 }
40
41 int main()
42 {
43 int T;
44 int n;
45 int i, j;
46 Node tmp;
47 set
48 int tmp2;//
49
50 scanf("%d", &T);
51
52 while (T--) {
53 //这样初始化超时
54 //memset(fa, -1, sizeof(fa));
55 //memset(childNum, 0, sizeof(childNum));
56 scanf("%d", &n);
57 memset(fa, -1, sizeof(int) * (n + 1));
58 memset(childNum, 0, sizeof(int) * (n + 1));
59 st.clear();
60 vt2.clear();
61 for (i = 0; i < n; ++i) {
62 scanf("%d", &a[i].val);
63 a[i].id = i + 1;
64 it = st.upper_bound(a[i]);
65 if (it == st.begin()) {//
66 st.insert(a[i]);
67 vt2.push_back(a[i].id);
68 vt[a[i].id].push_back(a[i].id);
69 } else {
70 tmp = *(--it);
71 setJoin(a[i].id, tmp.id);
72 ++childNum[tmp.id];
73 if (childNum[tmp.id] >= 2) {
74 st.erase(tmp);
75 }
76
77 vt[setFind(tmp.id)].push_back(a[i].id);//加到根节点孩子列表
78 st.insert(a[i]);
79 }
80 }
81
82 printf("%d\n", vt2.size());
83 for (i = 0; i < vt2.size(); ++i) {
84 tmp2 = vt2[i];//根节点
85 printf("%d", vt[tmp2].size());
86 printf(" %d", vt[tmp2][0]);//根节点
87 for (j = 1; j < vt[tmp2].size(); ++j) {//孩子节点
88 printf(" %d", vt[tmp2][j]);
89 }
90 printf("\n");
91 vt[tmp2].clear();//在这里清空比较好
92 }
93 }
94
95 return 0;
96 }
View Code
下面这个树状数组的没看懂，
思路：贪心，对于a[i],贪心的话就是要在a[1]~a[i-1]中找到一个a[j]做父亲（且a[j]不能超过两个孩子）,a[j]<=a[i]&&a[j]>=a[k](1<=任意k<=i-1,k!=j) 可以离散化，然后二分+树状数组找，线段树会T;
1 #include
2 using namespace std;
3 const int maxn=1e5+10;
4 template
5 char CH; bool F=false;
6 for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
7 for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
8 F && (num=-num);
9 }
10 int stk[70], tp;
11 template
12 if(!p) { puts("0"); return; }
13 while(p) stk[++ tp] = p%10, p/=10;
14 while(tp) putchar(stk[tp--] + '0');
15 putchar('\n');
16 }
17
18
19 int n,a[maxn],vis[maxn],p[maxn],b[maxn],sum[maxn];
20 vector
21 struct node
22 {
23 int a,id;
24 }po[maxn];
25 int cmp(node x,node y)
26 {
27 if(x.a==y.a)return x.id 28 return x.a 29 } 30 inline int lowbit(int x){return x&(-x);} 31 inline int query(int x) 32 { 33 int s=0; 34 while(x) 35 { 36 s+=sum[x]; 37 x-=lowbit(x); 38 } 39 return s; 40 } 41 inline void update(int x,int num) 42 { 43 while(x<=n) 44 { 45 sum[x]+=num; 46 x+=lowbit(x); 47 } 48 return ; 49 } 50 51 52 inline int solve(int x) 53 { 54 int l=1,r=b[x]-1; 55 while(l<=r) 56 { 57 int mid=(l+r)>>1; 58 if(query(b[x]-1)-query(mid-1)>0)l=mid+1; 59 else r=mid-1; 60 } 61 if(l-1<=0)return -1; 62 return p[l-1]; 63 } 64 int main() 65 { 66 int T; 67 scanf("%d",&T); 68 while(T--) 69 { 70 scanf("%d",&n); 71 for(int i=1;i<=n;i++)read(po[i].a),po[i].id=i,ve[i].clear(),sum[i]=0; 72 sort(po+1,po+n+1,cmp); 73 for(int i=1;i<=n;i++)b[po[i].id]=i,p[i]=po[i].id; 74 int ans=0; 75 for(int i=1;i<=n;i++) 76 { 77 int pos=solve(i); 78 if(pos==-1)ans++,vis[i]=ans,ve[ans].push_back(i); 79 else vis[i]=vis[pos],ve[vis[i]].push_back(i),update(b[pos],-1); 80 update(b[i],2); 81 } 82 printf("%d\n",ans); 83 for(int i=1;i<=ans;i++) 84 { 85 int len=ve[i].size(); 86 printf("%d",len); 87 for(int j=0;j 88 } 89 } 90 return 0; 91 } View Code 好文阅读
发表评论