ZOJ 3963 Heap Partition(贪心)

71 阅读 0 评论 47 点赞

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

概述

题意

构造二叉树，保证父节点的编号小于子节点且父节点的值小于子节点
求最少的二叉树个数，输出每棵二叉树

思路

对于当前的每个值，找到之前刚好小于等于他的值(upper_bound找到第一个大于x的位置)，作为子节点，因为可能出现重复的值而且子节点个数只有两个，当已经有两个子节点时，这个点可以不用再考虑

代码

#include <bits/stdc++.h>
#define sc(a) scanf("%d",&a)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<b;i++)
const int INF=0x3f3f3f3f;
const int maxn=1e5+50;
const int mod=1e9+7;
const double eps=1e-8;
typedef long long ll;
using namespace std;

struct D{
    int val,id,ansId;
    bool operator<(const D&rhs)const {
        if(val!=rhs.val) return val<rhs.val;
        return id<rhs.id;
    }
};

vector<int> ans[maxn];

void display(vector<int> &v){
    int sz=v.size();
    sort(v.begin(),v.end());
    printf("%d",sz);
    rep(i,0,sz){
        printf(" %d",v[i]);
    }
    puts("");
}

D s[maxn];
int n;

int main()
{
#ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
#endif
    int T; sc(T);
    while(T--){
        sc(n);
        rep(i,1,n+1){
            sc(s[i].val);
            s[i].id=i;
        }
        rep(i,0,n) ans[i].clear();
        set<D> se;
        map<int,int> ma;
        int tot=-1;
        rep(i,1,n+1){
            int id=s[i].id;
            D tmp=s[i];
            auto it=se.upper_bound(tmp);
            if(it==se.begin()){
                tot++;
                tmp.ansId=tot;
            }else{
                it--;
                tmp.ansId=it->ansId;
                ma[it->id]++;
                if(ma[it->id]==2){
                    se.erase(it);
                    ma[it->id]=0;
                }
            }
            //printf("id %d tot %d ansid %dn",id,tot,tmp.ansId);
            ans[tmp.ansId].push_back(id);
            se.insert(tmp);
        }
        printf("%dn",tot+1);
        rep(i,0,tot+1) display(ans[i]);
    }
    return 0;
}