忘了哪个地方忘了哪次考试创新题调整法

AzureHair · 2024-12-15 10:32:24 · 学习·文化课

简明题干：

在这样第一象限的这个三角形内 ( 含边界 ) 内有 n 个点，其中第 i 个点记为 (x_i,y_i)，现将这 n 个点划分成两个集合 A,B，记 A 集合中的点的横坐标之和为 X(A)，B 集合中的点的纵坐标之和为 Y(B)，求证存在一种划分方法，使得 X(A)\le \frac{n+1}{2}，Y(B)\le \frac{n+1}{2}。

我们先说一下当时我在做题时是怎样想到调整法的，当时看题后首先想到的是把它分成三个区域，这个是很自然的，因为我们最优的策略一定是把 x_i 较小的点放到 A 集合中，y_i 较小的点放到 B 集合中，而这样划分图 1,2 区域分别是满足 y_i>x_i 和 x_i>y_i 的区域，在这样区域中的数肯定会被优先分配到 A,B 集合中的。

这样之后我们就发现的一点小性质，首先是 1,2 区域是一种比较对称的存在，第二是这个 3 区域纯小丑，x_i,y_i 没有一个大的，到这里一个思路就呼之欲出了，构造最劣情况。

这个题目的要求是对于任意的点都能存在一组解，那么这个点的任意性就可以让我有很大的动手空间，我们只需要找到最劣的点的分布，并且在这样的分布下依然能够构造出解，我们就能说明这个结论。下面开始证明：

则将全部 x_i\le 1 的点划分进集合 A 中，此时 X(A)\le a

则 A 集合剩余元素横坐标之和 \sum x_i\le\frac{n+1}{2}-a

设满足的 x_i>1 的点的坐标为 (c_1,d_1),(c_2,d_2)\cdots (c_{n-a},d_{n-a}) 且 c_1\le c_2\le \cdots \le c_{n-a},d_1\ge d_2\ge\cdots\ge d_{n-a}

设满足 \sum_{i=1}^k c_i\le \frac{n+1}{2}-a 的最大 k 为 m

若 c_1<c_2，则令 c_1 增大至 c_2 更劣，同理得 c_1=c_2=\cdots=c_m

反之同理得 c_{m+1}=\cdots=c_{n-a}

若 c_m<c_{m+1}，则令 c_m 增大至 c_{m+1} 更劣

故 c_1=c_2=\cdots=c_{n-a} 最劣

不妨设 x=c_1,y=d_1,x+y=2

则只需证 y(n-a-\lfloor \frac{\frac{n+1}{2}-a}{x}\rfloor)\le \frac{n+1}{2} 即可