本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$ 的限制变宽，依次执行下列操作：

1. 强制交换的展板有一部分不再需要强制交换，原因是 $h \le lim$ 了，此时将它们从强制交换的 set 删除，当然，根据之前的定义，它们交换 $h,w$ 一定不优。
2. 另外，一些展板不允许交换 $h,w$，原因是 $w \gt lim$，此时它们变得可能交换，将他们加入允许交换的集合。
3. 一些不合法的集合变得合法，原因是此时 $\min(h,w) \le lim$ 了，分类讨论将它们归入允许交换或不允许交换的集合。
4. 在允许交换 $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;
}