BZOJ5289：[HNOI2018]排列

我对贪心的理解：https://www.cnblogs.com/AKMer/p/9776293.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=5289

首先我们转化题意：对于任意一个\(w_i\)，只能在\(w_{a_i}\)被取之后才能被取走。存在某一取法\(p\)使得\(\sum\limits_{i=1}^{i=n}i*w_{p_i}\)取值最大，求最大值。

对于每一个\(i\)与\(a_i\)的约束，我们可以建一条边来描述。那么这题就跟Color a Tree一模一样的，不过求的是最大值罢了，那我们每次选平均值最小的与父亲合并就行。如果不能构成树就无解，构成树或者森林就有解。我们以\(0\)为虚根，那么就必然是一棵树了。

如果不存在某个\(a_i\)等于\(0\)，或者存在\(a_i=i\)那么就肯定无解，否则必然有解。

然而知道这些你还是\(A\)不了这道题。若你问我而出此言，且听我细细道来：

\(1\)、平均值不开\(long\) \(double\)过不了；

\(2\)、平均值不开\(long\) \(double\)过不了；

\(3\)、平均值不开\(long\) \(double\)过不了；

重要的事情说三遍。

某出题人欺我老无力，

忍能偷偷卡精度。

公然卡我的double，

Bug连天改不出，

归来伏桌自叹息。

取最小值用堆维护一下，合并维护父亲信息用并查集就可以了。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <queue>

#include <cstdio>

#include <algorithm>

using namespace std;

#define ll long long

#define ld long double

const int maxn=5e5+5;

int n,tot;

ll w[maxn],ans;

bool bo1,bo2,vis[maxn];

int a[maxn],fa[maxn],num[maxn],father[maxn];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct node {

    int id;

    ld ave;

    bool operator<(const node &a)const {

        return ave>a.ave;//初始是大根堆，所以要反过来

    }

};

priority_queue<node> T;

int find(int x) {

    if(fa[x]==x)return x;

    return fa[x]=find(fa[x]);

}

void work() {

    for(int i=1;i<=n;i++)

        T.push((node){i,(ld)w[i]});

    while(!T.empty()){

        node N=T.top();int u=N.id;T.pop();

        if(vis[u])continue;vis[u]=1;//由于每次都是将最小值合并，所以越合并平均值也就会越小，那么我们只需要知道这个node是否是已经合并过的node就行了。对于任意一个没有合并但是被多次插入堆中的node，最新的一次插入肯定是平均值最小的那一次，所以每次取最小值肯定就是最新更新的数据。

        int FA=find(father[u]);

		ans+=w[u]*num[FA];fa[u]=FA;

        w[FA]+=w[u];num[FA]+=num[u];

        if(FA)T.push((node){FA,(ld)w[FA]/num[FA]});//具体请见color a tree

    }

}

int main() {

    n=read();num[0]=1;

    for(int i=1;i<=n;i++) {

        a[i]=read();num[i]=1;

		fa[i]=i;father[i]=a[i];//father记树上父亲节点，fa记录并查集祖先

        if(!a[i])bo1=1;

        if(a[i]==i)bo2=1;

    }

    if(!bo1||bo2) {puts("-1");return 0;}//判无解

    for(int i=1;i<=n;i++)

        w[i]=read();

    work();printf("%lld\n",ans);

    return 0;

}

巴特西

BZOJ5289：[HNOI2018]排列

最新文章

热门文章