ZOJ-3963-Heap Partition（贪心）（STL）

71 阅读 0 评论 47 点赞

我是靠谱客的博主勤劳凉面，最近开发中收集的这篇文章主要介绍ZOJ-3963-Heap Partition（贪心）（STL），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5595

大致题意：用给出的数列a1,a2,a3....an构造二叉树，满足对于下标i和j，有i<j 且ai<=aj满足ai是aj的父节点，问最少需要构造几棵树，并输出。

正序建树模拟一下，找到小于等于当前权值的一个可插入最大值，成为其子节点，找不到则新建树。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        vector<int> a(n), b(n), c(n);
        set< pair<int, int> > se;
        vector< vector<int> > ans;
        set< pair<int, int> >::iterator it;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            it = se.lower_bound( {-a[i], -i});
            if (it == se.end())
            {
                ans.push_back(vector<int>(1, i + 1));
                b[i] = ans.size() - 1;
            }
            else
            {
                ans[b[-it->second]].push_back(i + 1);
                b[i] = b[-it->second];
                c[-it->second]++;
                if (c[-it->second] == 2)
                    se.erase(it);
            }
            se.insert( {-a[i], -i});
        }
        printf("%dn", (int)ans.size());
        for(int i=0,N=ans.size(); i<N; ++i)
        {
            printf("%d", (int)ans[i].size());
            for(int j=0,M=ans[i].size(); j<M; ++j)
                printf(" %d", ans[i][j]);
            puts("");
        }
    }
    return 0;
}