题解P6787 【Snow Mountain】

sfmmdm · 2020-08-23 23:30:51 · 题解

首先，我们假设，没有不能配对的水晶，那么我们可以很容易想到一个贪心思路：

因为每次只计算能量值小的水晶，也就是说，只要排序后在前 \dfrac{n}{2} （以下简称“前半段”）个数中找数和后 \dfrac{n}{2} （以下简称“后半段”）随便找一个数配对即可，而且要从大到小选择。

简单证明一下，首先第一个很显然，如果把其中两对按“一前一后”配对的数换成“两前”和“两后”，那结果就由两个在前半段的数换成一个后半段和前半段的数统计而来，很明显不是最优的。

第二个，这个可以联系“排队接水”问题的贪心策略，假设我们给能量值为 x 和 y 的两个出现在前半段的水晶分别在第 k 和 k+1次销毁（后半段的很明显不用考虑），若 x<y，那么

先销毁 x 再销毁 y 的代价：

先销毁 y 再销毁 x 的代价：

因为 x<y，所以很明显先销毁大的更优。

现在加入了限制条件，说有些水晶不能同时销毁，但是，题目还有一个很重要的条件：对于每个水晶，有很多不能和它一起销毁，但其中能量值比它大的只有一个。

如果一个水晶不能和所有水晶配对，那此情况无解，除此之外，不存在无解的可能，因为这些不能配对的水晶最多只能连成一棵树，除了菊花图以外，不可能找到有点无法配对的情况，只要顺序合理，一定有解。

我们称有和后半段水晶不能配对的前半段水晶称为“锁定的水晶”，配对一对水晶，让前半段的一些水晶不被锁定称为“解锁”（当时我思考时用的词，这里顺着思路说下来）

而我们只要将“一前一后”地配对，而后半段的水晶无论怎么选都不会影响结果，所以只要后半段不存在能锁定前半段全部水晶的水晶，就一定可以一前一后地配对完所有水晶，而不会影响结果。

至于这种情况的构造方法，很明显，只要保证后半段没有水晶会锁定前半段剩余所有水晶即可。在此基础上思考构造策略即可，为方便实现，我们在每次配对时，都选择能解锁水晶最多的水晶。

如果有一颗后半段的水晶锁定了前半段所有水晶，我们只要先用一个能与这个水晶配对的最小的水晶先与之配对，一定要先配这对，因为很明显这对的能量值是最大的。

很明显这对水晶一定是后半段的，然后我们只要将分界点前移，此时前半段所有点都已被解锁，接下来就可以完全自由地配对了。

#include <bits/stdc++.h>
#include <queue>
using namespace std;
int n;
bool flag;
struct crystal {
    int a,x,cnt,pos;//a,x为题目意思，cnt为比它小的水晶和它不能配对的个数，pos为排序前水晶的编号
} b[500005];
bool cmp(const crystal &x, const crystal &y) {
    return x.a<y.a;
}
bool operator <(const crystal &x, const crystal &y) {
    if(x.cnt==y.cnt) return x.a>y.a
    return x.cnt<y.cnt;
}
long long ans;
priority_queue <crystal> h;//注意我在实现时优先队列是以cnt排序的，而cnt并不等于锁定的水晶数（就是这里的策略和前面说的略有不同），但这种策略也是可以保证出解的，为方便实现这里就用这种。
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&b[i].a);
    for(int i=1; i<=n; i++) scanf("%d",&b[i].x);
    for(int i=1; i<=n; i++) b[i].pos=i;
    if(n==2) {
        if(b[1].x==-1&&b[2].x==-1) printf("%d\n1 2\n",min(b[1].a,b[2].a));
        else printf("-1\n");
        return 0;
    }
    for(int i=1; i<=n; i++) if(b[i].x!=-1) b[b[i].x].cnt++;
    sort(b+1,b+n+1,cmp);
    for(int i=(n>>1)+1; i<n; i++) {
        h.push(b[i]);
    }
    if(h.top().x!=-1&&h.top().cnt==n-2) {//最后一个水晶暂不入堆，此时倒数第二水晶点cnt为n-2且x不为-1就表示它和所有水晶都无法配对。
        printf("-1\n");
        return 0;
    }
    h.push(b[n]);
    if(h.top().cnt==n-1) {//最后一个水晶如堆后，如果cnt==n-1，就代表它无法和前面的所有水晶配对
        printf("-1\n");
        return 0;
    }
    crystal t=h.top();//只有cnt最多的水晶才可能锁定前半段的所有水晶
    for(int i=1; i<=(n>>1); i++) {
        if(b[i].x!=t.pos) flag=1;
    }
    if(flag) {
        for(int i=(n>>1); i>=1; i--) {
            ans+=1ll*((n>>1)-i+1)*b[i].a;
        }
        printf("%lld\n",ans);
        for(int i=(n>>1); i>=1; i--) {
            t=h.top();
            if(b[i].x!=t.pos) {
                printf("%d %d\n",b[i].pos,t.pos);
                h.pop();
            } else {//如果cnt最大的水晶不能和改水晶配对，那第二大的一定可以（我们只对后半段的水晶入堆）
                h.pop();
                printf("%d %d\n",b[i].pos,h.top().pos);
                h.pop();
                h.push(t);
            }
        }
    } else {
        int p;
        for(p=(n>>1)+1; p<=n; p++) {
            if(b[p].a<t.a) {
                if(b[p].x!=t.pos) break;
            }
            if(b[p].a>t.a) {
                if(t.x!=b[p].pos) break;
            }
        }
        ans+=min(b[p].a,t.a);
        for(int i=(n>>1)-1; i>=1; i--) {
            ans+=1ll*((n>>1)-i+1)*b[i].a;
        }
        printf("%lld\n",ans);
        printf("%d %d\n",t.pos,b[p].pos);
        h.pop();
        for(int i=(n>>1)-1,j=n>>1; j<=n&&i>=1; i--,j++) {//一定注意分界点换了
            if(j==p||b[j].a==t.a) j++;
            printf("%d %d\n",b[i].pos,b[j].pos);
        }
    }
    return 0;
}

还没完，这里补充一下每次选择 cnt 最大的水晶的正确性证明。(cnt 含义看代码注释)

假设在某一时刻，前后半段剩余 x 个水晶，前半段最多有 k 个水晶被同一水晶锁定。

假设 x-k>1，则后半段配对的水晶可以自由选择。

假设 x-k=1，则锁定前半段水晶为 k 的水晶的 cnt \ge x-1，而后半段的水晶除了最后一个，所有 cnt < x-1。

我们只要在这种情况避免选到最后一个即可。