[ARC073C] Ball Coloring

简要题意

\(N\) 个盒子，每个盒子里有两个数。现在要把盒子中的数分成两种颜色，满足：
1. 每个盒子中的数分别属于两种颜色，每个数恰好属于一种颜色
1. 两种颜色的数的极差的乘积最小
求这个最小值
\(N \le 200000\)

分析与解答

考虑极差的乘积的最小值，要么是让其中一个极小；要么是让两个都尽量小，感性理解即可

下文记 \(x_i\) 表示第 \(i\) 个盒子的较小值，\(y_i\) 表示第 \(i\) 个盒子的较大值。

分类讨论最大值和最小值是不是同色

1. 最大值和最小值不同色

这时让两个极差都尽量小

所以把所有 \(y_i\) 染成同一种颜色，所以 \(x_i\) 染成另一种颜色。

证明考虑交换一对 \(x_i\)、\(y_i\)，比较简单，也很好理解，这里就不写了。

2. 最大值和最小值同色

此时，其中一种颜色的极差已经固定，为所有数的极差，我们的目标是让另一种颜色的极差尽量小。

下面记 选一个盒子 表示把这个盒子的 \(x_i\) 划分到另一种颜色，这种颜色(即上文另一种颜色)的其余部分由其余盒子的 \(y_i\) 组成。

首先将盒子按照 \(x_i\) 排序

此时可以证明，选出的盒子一定是从某个位置 \(p\) 开始的一段后缀 \((p > 1)\)

证明如下：

假设当前选了后 \(p\) 个盒子。由于按照 \(x_i\) 排过序，所以最大值为 \(maxx = \max(x_n, \max\{y_i\})\)，最小值为 \(minn = \min(x_p, \min\{y_i\})\)。记此时极差
若在前 \(n-p\) 个位置中，还选了一个盒子 \(k\)。则此时最大值 \(maxx^{'} = maxx\)，最小值 \(minn^{'}= \min(x_k, \min\{y_i\})\)
还是由于 \(x_i\) 有序，所以 \(minn^{'} \le minn\)。所以不选 \(k\) 时，极差不会比选 \(k\) 更大。
所以选的一定是一段后缀

所以枚举 \(p\)，维护 \(y_i\) 的前缀最大值和前缀最小值即可。

记得和第一种情况取最小值。

Code

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 200010;

const int INF = 0x3f3f3f3f;

int n;

struct ball{

	int x, y;

	ball(int X=0,int Y=0):x(X),y(Y){}

	inline bool operator<(const ball&o)const{return x<o.x;}

}a[MAXN];

int main()

{

//	freopen("ball.in","r",stdin);

//	freopen("ball.out","w",stdout);

	scanf("%d",&n);

	int maxx = 0, minx = INF, maxy = 0, miny = INF;

	for(int i=1,u,v;i<=n;i++)

	{

		scanf("%d%d",&u,&v);

		a[i].x = min(u, v);

		a[i].y = max(u, v);

		maxx = max(maxx, a[i].x);

		minx = min(minx, a[i].x);

		maxy = max(maxy, a[i].y);

		miny = min(miny, a[i].y);

	}

	ll ans = 1ll*(maxx-minx)*(maxy-miny);

	ll val1 = maxy - minx;

	sort(a+1, a+n+1);

	minx = INF; maxx = 0;

	for(int i=1;i<n;i++)

	{

		minx = min(minx, a[i].y);

		maxx = max(maxx, a[i].y);

		ans = min(ans, val1*(max(maxx, a[n].x) - min(minx, a[i+1].x)));

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西