Description

有一个 $n\times m$ 的数表 $a$，$a_{i,j}=(i-1)\times m+j$。

现在将这个数表分成两个数表 $x,y$，使得 $\max\{\sum x,\sum y\}$ 最小。同时输出分割的方法。

Analysis

题目要求 $\max\{\sum x,\sum y\}$ 最小，同时又知道 $\sum x+\sum y$ 固定，所以我们要求最小的 $\lvert \sum x-\sum y\rvert$，使得 $\sum x$ 和 $\sum y$ 的值尽量接近，这样 $\max\{\sum x,\sum y\}$ 才能尽可能的小。

Solution

不妨以竖切为例，横切同理。

设 $L(x)$ 表示前 $x$ 列的和，在 $i$ 行后切最优，则 $\sum x=L(i),\sum y=L(m)-L(i)$，所以 $\lvert \sum x-\sum y\rvert=\lvert 2 \times L(i)-L(m)\rvert$。又知 $L(m)$ 为定值，$L(i)$ 单调上升，所以 $\lvert \sum x-\sum y\rvert$ 的值就是一个单调上升的值减去一个定值的绝对值。这不就是单谷函数吗？

所以本题可以用三分求解。不会三分请左转。

三分过程不再详细赘述，现在先解决一个问题，如何在短时间内求出 $L(i)$ 呢？我想到过用前缀和预处理再 $\mathcal{O(1)}$ 查询，但预处理的时间和空间复杂度都很大，于是果断放弃。

我们可以简单地推一个式子。先拿 $3 \times 5$ 的数表举例：

$$\begin{bmatrix}1&2&3&4&5\\6&7&8&9&10\\11&12&13&14&15\end{bmatrix}$$

我们试求一下 $L(3)$。第 $1$ 列的数组成等差数列，首项为 $1$，项数为 $3$，公差为 $5$，所以末项为 $1+5\times(3-1)=11$。用等差数列求和公式即可得出这一列的和为 $(1+11)\times 3 \div 2=18$。第 $2$ 列中每一个数都比第 $1$ 列中和自己同一行的数大 $1$，又因为每一列有 $3$ 个数，所以第 $2$ 列的总和比第 $1$ 列大 $1 \times 3$。同理，第 $3$ 列的总和比第 $1$ 列大 $2 \times 3$。所以 $3$ 列总和即为 $3 \times L(1)+1\times 3+2\times 3$，即 $L(3)=3\times 18+(1+2)\times 3$。

推广至在 $n\times m$ 的数表中求 $L(i)$，不难得出如下代码：

int Cal_L(int x){//求L(x)
	int L1=(n*m-m+2)*n/2;//L1=(1+1+m*(n-1))*n/2=(n*m-m+2)*n/2
	int ans=L1*x+x*(x-1)/2*n;//Lx=L1*x+(1到x-1之和)*n=L1*x+(x-1)*x/2*n
	return ans;
}

所有问题就迎刃而解了。

横切的思考方式同理，留与读者自行推导。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,m;
int Cal_L(int x){//求L(x)
	int L1=(n*m-m+2)*n/2;//L1=(1+1+m*(n-1))*n/2=(n*m-m+2)*n/2
	int ans=L1*x+x*(x-1)/2*n;//Lx=L1*x+(1到x-1之和)*n=L1*x+(x-1)*x/2*n
	return ans;
}
int Cal_H(int x){//同理
	int H1=(1+m)*m/2;
	int ans=H1*x+x*(x-1)/2*m*m;
	return ans;
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		//以下就是三分板子力
		int lt=1,rt=m;
		while(lt<rt){
			int lmid=lt+(rt-lt+1)/3,rmid=lt+(rt-lt+1)*2/3;
			int lans=abs(Cal_L(lmid)*2-Cal_L(m));
			int rans=abs(Cal_L(rmid)*2-Cal_L(m));
			if(lans<=rans)
				rt=rmid-1;
			else
				lt=lmid+1;
		}
		int Lans=abs(Cal_L(rt)*2-Cal_L(m)),Lpos=rt;
		lt=1,rt=n;
		while(lt<rt){
			int lmid=lt+(rt-lt+1)/3,rmid=lt+(rt-lt+1)*2/3;
			int lans=abs(Cal_H(lmid)*2-Cal_H(n));
			int rans=abs(Cal_H(rmid)*2-Cal_H(n));
			if(lans<=rans)
				rt=rmid-1;
			else
				lt=lmid+1;
		}
		int Hans=abs(Cal_H(rt)*2-Cal_H(n)),Hpos=rt;
		if(Lans<=Hans)//比较竖切横切谁更优
			cout<<"V "<<Lpos+1<<"\n";
		else
			cout<<"H "<<Hpos+1<<"\n";
	}
	return 0;
}