题意

二维平面上有\(n(2 \le n \le 1000000)\)个点，可以花费\(w_i\)交换第\(i\)个点的横纵坐标。求在满足能覆盖所有点的最小矩阵周长最短的情况下花费最小。

分析

这题太神了。有一个结论是，所有点都会交换到\(y=x\)线的同一侧。

题解

所以我们暴力就行辣。

#include 
    
     using namespace std;inline int getint() {    int x=0, c=getchar();    for(; c<48||c>57; c=getchar());    for(; c>47&&c<58; x=x*10+c-48, c=getchar());    return x;}const int N=1000005;bool ok[N], vi[N];int n, x[N], y[N], w[N], ans=~0u>>1;void go(int lx, int rx, int ly, int ry) {    int temp=0;    for(int i=1; i<=n; ++i) {        if(lx<=x[i] && x[i]<=rx && ly<=y[i] && y[i]<=ry) {            vi[i]=0;        }        else if(lx<=y[i] && y[i]<=rx && ly<=x[i] && x[i]<=ry) {            vi[i]=1;            temp+=w[i];        }        else {            return;        }    }    if(temp
     
      >1, ly=lx, rx=-lx, ry=rx;    for(int i=1; i<=n; ++i) {        x[i]=getint(), y[i]=getint(), w[i]=getint();        int a=min(x[i], y[i]), b=max(x[i], y[i]);        lx=min(lx, a);        rx=max(rx, a);        ly=min(ly, b);        ry=max(ry, b);    }    printf("%lld ", 2ll*(rx-lx+ry-ly));    go(lx, rx, ly, ry);    go(lx, ry, ly, rx);    go(ly, rx, lx, ry);    go(ly, ry, lx, rx);    printf("%d\n", ans);    for(int i=1; i<=n; ++i) {        putchar('0'+ok[i]);    }    return 0;}