【BZOJ】1105: [POI2007]石头花园SKA

题意

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

分析

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

题解

所以我们暴力就行辣。

#include <bits/stdc++.h>

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<ans) {

		ans=temp;

		memcpy(ok, vi, sizeof(bool)*(n+1));

	}

}

int main() {

	n=getint();

	int lx=~0u>>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;

}

巴特西

【BZOJ】1105: [POI2007]石头花园SKA

题意

分析

题解

最新文章

热门文章