ZOJ3963 Heap Partition

初始化for0~N会超时

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl

const int N=100005;
vector<int> ans[N];
set<pair<int,int> > s;
bool vis[N];
int pre[N],a[N],son[N];

int find(int x) {
    if(x==pre[x]) return x;
    return pre[x]=find(pre[x]);
}
void join(int x,int y) {
    int fx=find(x),fy=find(y);
    pre[fx]=fy;
}

int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///read
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i) {
            scanf("%d",a+i);
            son[i]=2;
        }

        ///init
        for(int i=1;i<=n;++i) {
			pre[i]=i;
			vis[i]=0;
			ans[i].clear();
		}
        s.clear();

        ///solve
        for(int i=1;i<=n;++i) {
            set<pair<int,int> >::iterator it=s.upper_bound( mp(a[i],i) );
            if(it==s.begin()) {
                s.insert( mp(a[i],i) );
            } else {
                it--;
                pair<int,int> now=*it;
                --son[now.se];
                if(son[now.se]==0) s.erase( it );
                s.insert( mp(a[i],i) );
                join(i,now.se);
            }
        }

        ///print
        int res=0;
        for(int i=1;i<=n;++i) {
            int t=find(i);
            if(!vis[t]) ++res;
            vis[t]=1;
            ans[t].pb(i);
        }

        printf("%dn",res);
        for(int i=1;i<=n;++i) {
            if(!vis[i]) continue;
            int sz=ans[i].size();
            printf("%d ",sz);
            for(int j=0;j<sz;++j) printf("%d%c",ans[i][j],(j==sz-1)?'n':' ');
        }

    }
    return 0;
}

最后

以上就是魔幻音响为你收集整理的ZOJ3963 Heap Partition的全部内容，希望文章能够帮你解决ZOJ3963 Heap Partition所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。