UESTC 1603 BanG Dreamer 小根堆、贪心+set>+low_bound

BanG Dreamer 小根堆、贪心

Source

17暑假前集训-数据结构专题 By AutSky_JadeK

2017 UESTC Training for Data Structures

UESTC 1603 BanG Dreamer

My Solution

题意：给出一个序列，要求划分成尽可能少的堆序列。
一个序列S={s1,s2,...,sn}S={s1,s2,...,sn}是一个“堆型序列”当且仅当，存在一个有nn个结点的二叉树，其每个结点与该序列的元素一一对应，
而且对于该二叉树的每个非根结点sisi和它的父节点sjsj，满足sj≤sisj≤si并且j<ij<i。
子序列的定义是，其是某个序列删除掉任意数量元素之后，所剩下的部分。并且不改变其原有的顺序。

小根堆、贪心+set<pair<int, int>>+low_bound
用set维护，set中存储的是个pair第一维权值，第二维是在原序列的下标。、

pair的比较函数是双关键字比较，先按第一关键字，如果相同，再按第二关键字。

贪心地从前往后扫，每到一个元素，就查找之前的元素中小于等于其的最大的元素
ptr = s.lower_bound(ii（a[i],i));ptr--;
这里必须用set的成员函数 low_bound，不能用泛型函数low_bound。
如果存在，就将它置为其父亲，存储在邻接表vector sons[MAXN]里。
1）如果一个结点已经是两个儿子的父亲了，就不能在set中存在了，就将他删除。
然后将当前元素插入。

2）如果不存在，就直接将当前元素插入。

证明是比较显然的，因为对于某个元素，前面各个堆中权值相同的结点都是等价的。

输出答案时跑个dfs并标记丢小根堆里，每个堆分别输出即可。
复杂度 O(nlogn)

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
const int MAXN = 1e5 + 8;

vector sons[MAXN];
set s;
priority_queue<int, vector, greater> pq;
int a[MAXN], vis[MAXN], f[MAXN], T;

inline void dfsvis(int u, int fa)
{
    int sz = sons[u].size(), i;
    vis[u] = T + 1;
    for(i = 0; i < sz; i++){
        if(sons[u][i] == fa) continue;
        dfsvis(sons[u][i], u);
    }
}

inline void dfs(int u, int fa)
{
    int sz = sons[u].size(), i;
    pq.push(u); f[u] = T + 1;
    for(i = 0; i < sz; i++){
        if(sons[u][i] == fa) continue;
        dfs(sons[u][i], u);
    }
}

int main()
{
    #ifdef LOCAL
    freopen("i.txt", "r", stdin);
    //freopen("i.out", "w", stdout);

    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, i, ans;
    set::iterator ptr;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        s.clear();
        s.insert(ii(a[1], 1));
        for(i = 2; i <= n; i++){
            ptr = s.lower_bound(ii(a[i], i));

            if(ptr == s.begin()){
                s.insert(ii(a[i], i));
            }
            else{
                ptr--;
                //cout << ptr->first << " " << ptr->second << endl;
                //cout << ptr->second << endl; sons[ptr->second].push_back(i);
                if(sons[ptr->second].size() == 2){
                    s.erase(ptr);
                }
                s.insert(ii(a[i], i));
            }
        }

        ans = 0;
        for(i = 1; i <= n; i++){
            if(vis[i] == T + 1) continue;
            dfsvis(i, -1);
            ans++;
        }
        printf("%dn", ans);
        for(i = 1; i <= n; i++){
            if(f[i] == T + 1){
                sons[i].clear();
                continue;
            }
            dfs(i, -1);
            printf("%d", pq.size());
            while(!pq.empty()){
                printf(" %d", pq.top());
                pq.pop();
            }
            putchar('n');
            sons[i].clear();
        }

    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx