CF529B 题解

__vector__ · 2025-01-17 21:27:23 · 题解

模拟赛数据范围看成了 10^5，苦战 2h 得以战胜，好像爆标了官方 std？

正文

考虑要维护哪些信息。

首先按照套路，升序枚举每个可能的最大的 h，设当前枚举的最大 h 为 lim。

现在，需要知道的是，有哪些展板必须翻转，使得不超过最大的 h。

如果存在一个展板无论如何，都不能靠翻转使得 h \le lim，那么当前无解，判定条件是 \min(h,w)\gt lim。

所以，维护一个 set 存储所有尚不合法的展板，第一关键字是 \min(h_i,w_i)，每次枚举 lim 都更新这个 set。

当不合法的展板全部清空之后，考虑如何翻转这些展板。

对于一个满足 w \gt h 的展板，如果能将 w,h 交换之后满足 h \le lim，那么交换之后，w 将减少 w-h，使得当前情况的答案减少 (w-h)lim。

但是，很多个展板都可能交换 h,w，得考虑哪些是真正需要交换的。

注意到，对于满足 w \le lim \lt h 的展板，属于必须翻转。

对于剩下的名额，则优先给 w-h 更大的展板。

考虑维护一个 set 存储所有可能交换 h,w 的展板（不含强制交换），第一关键字是 w-h；再用一个 set 维护所有强制交换的展板，第一关键字是 h；再用一个 set 维护所有不允许交换的展板，第一关键字是 w。

考虑如何更新这些 set。

每次更新 lim 时，由于对 h 的限制变宽，依次执行下列操作：

强制交换的展板有一部分不再需要强制交换，原因是 h \le lim 了，此时将它们从强制交换的 set 删除，当然，根据之前的定义，它们交换 h,w 一定不优。
另外，一些展板不允许交换 h,w，原因是 w \gt lim，此时它们变得可能交换，将他们加入允许交换的集合。
一些不合法的集合变得合法，原因是此时 \min(h,w) \le lim 了，分类讨论将它们归入允许交换或不允许交换的集合。
在允许交换 h,w 的集合里面选择前 \lfloor \frac{n}{2} \rfloor 大的，前提是 h-w \le 0，事实上前面加集合的时候就可以判断这点。另外，考虑用两个 set 维护允许交换 h,w 的集合，小的那个的大小维持在 \lfloor \frac{n}{2} \rfloor 及以下。

注意到，总共出现过 5 个 set，单个元素不可能被加入同一个 set 两次（除了允许交换的集合内部的两个 set，但是新加入一个元素最多造成 1 的影响），所以复杂度 O(n \log n)。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const int maxn=1005;
int n;
pll nd[maxn];
set<pll> notok;
set<pll> waitswp;// 交换之后更优，但是不可以交换，关键字 w
multiset<ll> canswp;// 可以交换，关键字 h-w
multiset<ll> canswp2;
set<pll> noswp;// 可能不需要交换，但强制交换，关键字 h 
int k=n/2;
ll w=0;
void solve(int id_of_test){
    read(n);
    vi ableh;
    FOR(i,1,n){
        read(nd[i].fi);
        read(nd[i].se);
        ableh.eb(nd[i].fi);
        ableh.eb(nd[i].se);
        notok.insert(mkpr(min(nd[i].fi,nd[i].se),i));
    }
    sort(ableh.begin(),ableh.end());
    ll ans=1e18;
    for(int h:ableh){
        while(!noswp.empty()){
            if(noswp.begin()->fi<=h){
                int id=noswp.begin()->se;
                if(nd[id].se>=nd[id].fi){
                    w-=nd[id].se;
                    w+=nd[id].fi;
                }else{
                    canswp.insert(nd[id].se-nd[id].fi);
                }
                noswp.erase(noswp.begin());
            }else break;
        }
    //  puts("???1");
        while(!waitswp.empty()){
            if(waitswp.begin()->fi<=h){
                int id=waitswp.begin()->se;
                canswp.insert(nd[id].se-nd[id].fi);
                w+=(nd[id].se-nd[id].fi);
                waitswp.erase(waitswp.begin());
            }else break;
        }
    //  puts("???2");
        while(!notok.empty()){
        //  puts("wtf");
            if(notok.begin()->fi<=h){
                int id=notok.begin()->se;
                if(nd[id].se<=h){
                    w+=nd[id].fi;
                    if(nd[id].fi>nd[id].se){
                        if(nd[id].fi>h){
                            waitswp.insert(mkpr(nd[id].fi,id));
                        }else{
                            w+=(nd[id].se-nd[id].fi);
                            canswp.insert(nd[id].se-nd[id].fi);
                        }
                    }

                }else{
                    if(nd[id].fi<=h){
                        w+=nd[id].se;
                        noswp.insert(mkpr(nd[id].se,id));
                    }else{
                        break;
                    }
                }
                notok.erase(notok.begin());
            }else break;
        }
        if(!notok.empty())continue;
        while(!canswp.empty()&&canswp.size()+noswp.size()>n/2){
            w-=*prev(canswp.end());
            canswp2.insert(*prev(canswp.end()));
            canswp.erase(prev(canswp.end()));
        }
        while(!canswp2.empty()&&canswp.size()+noswp.size()<n/2){
            w+=*canswp2.begin();
            canswp.insert(*canswp2.begin());
            canswp2.erase(canswp2.begin());
        }
    //  printf("w %lld\n",w);
        if(canswp.size()+noswp.size()>n/2)continue;
        ckmn(ans,w*h);
    }
    printf("%lld\n",ans);
}
int main()
{
    int T;
    T=1;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}