CF2222B Artistic Balance Tree 题解

· · 题解

思路

由于希望最后未被标记的元素总和最小，可以贪心地考虑标记尽可能大的元素。

一个关键的观察是：以任何一点 u 为中心翻转 [u-y,u+y] 后，被翻转部分的所有下标奇偶性不变。此时显然可以通过一次翻转操作将任意两个下标奇偶性相同的位置互换。

因此考虑分别按值降序维护下标为奇数的元素以及下标为偶数的元素，从大到小标记即可。举个例子：若原序列为 1,2,3,4,5,6,7，本次标记位置 3，则 1,3,5,7 都可以通过一次操作交换到位置 3 上，显然标记 7 最优。

但是还有一个非常重要的点：元素有可能是负数。此时考虑重复标记非负元素，即当所有非负元素标记完后，就不用考虑再标记负的了。仅有一种特例：下标为奇数或偶数的位置上不存在非负数，此时必须至少标记一个最大的负数。

代码

AC 记录

#include<bits/stdc++.h>
using namespace std;
const int NR=1e5+5;
int T;
int n,m;
void solve(){
    scanf("%d %d",&n,&m);
    priority_queue<int> q1,q2;
    long long ans=0;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        if(i&1) q1.push(x);
        else q2.push(x);
        ans+=x;
    }
    bool f1=0,f2=0;//记录奇/偶位置是否被标记过
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        if((x&1)&&!q1.empty()){//判奇偶性以及非空！
            if(q1.top()>0||!f1){//防止因为全是负数而漏标1个
                ans-=q1.top();
                q1.pop();
                f1=1;
            }
        }
        else if(!(x&1)&&!q2.empty()){//一定要判非空，不然吃罚时吃死(((
            if(q2.top()>0||!f2){//同上
                ans-=q2.top();
                q2.pop();
                f2=1;
            }
        }
    }
    printf("%lld\n",ans);
}
int main(){
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}

后话

我做的时候真的以为这玩意跟文艺平衡树有关 :(。