P3933 Chtholly Nota Seniorious

题目背景

大样例下发链接: https://pan.baidu.com/s/1nuVpRS1 密码: sfxg

こんなにも、たくさんの幸せをあの人に分けてもらった

だから、きっと

今の、私は

谁が何と言おうと

世界一、幸せな女の子だ

题目描述

——“假如……我是说假如喔。

万一我再过五天就会死，你能不能对我温柔一点？”

巨大的六号兽五天后将袭击浮游大陆。

无数次计算得到的残酷数据表明，只有圣剑瑟尼欧尼斯的适格精灵——珂朵莉·诺塔·瑟尼欧尼斯(Chtholly Nota Seniorious)开启妖精乡之门，才可以以生命为代价守住浮游岛。

“至少，我也希望自己不用消失，也想让别人记住。我也想留下羁绊啊。”

留给妖精少女珂朵莉的时间似乎已经不多了。

年轻的二等技官，妖精仓库的管理员，世界上最后一个人类——威廉·克梅修，数百年前曾经是一名准勇者，掌握着成为一名勇者所需要的所有知识。

大战在即，调整圣剑的状态成为了一项重要的任务。

瑟尼欧里斯（セニオリス）
圣剑的其中之一，在现存的遗迹兵装中，拥有最强大的力量。
拥有非常特殊的资质，只有极少一部分的人才能使用。
由四十一个护符组成。能将所有事物包含不死者都回归「死亡」。

威廉需要调整圣剑的状态，因此他将瑟尼欧尼斯拆分护符，组成了一个nn 行mm 列的矩阵。

每一个护符都有自己的魔力值。现在为了测试圣剑，你需要将这些护符分成 A,B两部分。

要求如下：

1. 圣剑的所有护符，恰好都属于两部分中的一部分。
2. 每个部分内部的方块之间，可以通过上下左右相互到达，而且每个内部的方块之间互相到达，最多允许拐一次弯。

例如

ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＡＡＡＡＡ
ＡＡＢＡＡ　　ＢａＡＡＡ　　ＡＡＡＢＢ
ＡＢＢＢＡ　　ＢＢＡＡＡ　　ＡＡＡＢＢ
ＡＡＢＡＡ　　ＢａＡＡＡ　　ＡＢＢＢＢ
ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＢＢＢＢＢ

　　(1)　　　　　(2)　　　　　(3)　　　　　　

其中(1)(2)是不允许的分法，(3)是允许的分法。在(2)中，a属于A区域，这两个a元素之间互相到达，没有办法最多只拐一次弯。

现在要问，所有合法的分法中，A区域的极差与B区域的极差 中间较大的一个的 最小值 是多少？

好心而可爱的在一旁默默观察奈芙莲悄悄地告诉你，极差就是区域内最大值减去最小值。

夜晚的风吹拂着，68号岛上的景色竟与地上的森林无异。转念又想，黄金妖精本身就是与森林之中出现，成长，消亡的神秘存在啊。

时间不早了，早上训练中落败的珂朵莉即将回来了。您要尽快和威廉一起调整好圣剑，千万不能迟哟。

输入输出格式

输入格式：

第一行两个自然数,

接下来n 行，每行m 个自然数 表示权值

输出格式：

一个整数表示答案。

输入输出样例

输入样例#1：

复制

4 4
1 12 6 11
11 4 2 14
10 1 9 20
4 17 13 10

输出样例#1：

复制

11

说明

样例解释

1  12 6        11
11 4  2        14
10 1  9        20
4        17 13 10

分法不唯一，如图是一种合法的分法。左边部分极差12-1=11，右边一块极差20-10=10，所以答案取这两个中较大者11。没有别的分法，可以使答案更小。

数据范围与约定

测试点	n	m
#1-2
#3-4
#5-7
#8-10

对于所有的权值

《末日时在做什么？有没有空？可以来拯救吗？》

看题比看番刺激系列

胡乱分析

翻译题意

最大的最小肯定是二分啊.

二分极值,然后check.

完

好下面考虑check怎么写.

先解释一下题目分割的要求.

根据题目描述,可以把要求抽象一下:

用一条折线,在图中将所有的AB分开,且分割线要么不拐弯,要么只能向一个方向拐弯.

这是一个不合法的情况,因为分割线在既背着第一列方向拐了又向着第一列方向拐了几次.

这是一个合法的情况,因为分割线从上到下看只向着第一列拐.

同样,旋转一下这条分割线也是合法的.

换一种说法,这条分割线除了两端,没有最上或最下或最左或最右.

ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＡＡＡＡＡ
ＡＡＢＡＡ　　ＢａＡＡＡ　　ＡＡＡＢＢ
ＡＢＢＢＡ　　ＢＢＡＡＡ　　ＡＡＡＢＢ
ＡＡＢＡＡ　　ＢａＡＡＡ　　ＡＢＢＢＢ
ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＢＢＢＢＢ

　　(1)　　　　　(2)　　　　　(3)　　　　　　

再根据这几个样例,基本题意就可以理解了吧.

基础的错误算法

刚开始拿到这题的时候,没什么思路的我准备瞎写个算法:

无视任何规则,从第一行第一列开始,按照从左到右,从上到下的方向以此考虑每个元素是否可以加入A集合,如果这个元素可以被加入A集合,更新目前已经选的元素组成的A集合的最大值和最小值,再考虑下一个元素.直到该元素不能加入A集合时,判断剩下的集合的极差是否在可接受的范围内.

很明显,这个方法有一个简单的反例.

 1 1 1 6
-2 9 9 9

假如可以容忍的极差为5,这种方法考虑到6这个元素的时候,由于目前选的A集合的最小值为1,所以6加入A集合,但是此时最大值要更新为6;

但是当考虑到-2这个元素时,由于最大值已经被更新为6,-2是加入不到A集合的.

此时检查剩下的四个元素,极差为11,不能接受,好像并不存在一种分法能把极差降到5以下.

但是一眼可以看出,存在一种分法能把两个集合极差变为3和3(太显然了我不画了).

考虑为什么会错

重点就在那个6上,简单说,就是明明不该放到A集合的元素硬拉进来且更新了最大值最小值,导致应该在A集合的元素不能加入A集合.

换句话说在枚举过程中,在枚举完所有一定要加入A集合的元素之前枚举到了可以不加入A集合的元素,即枚举顺序错误

换一种枚举顺序?

考虑分割线的限制,再换一种说法:

为了方便,现在只讨论形如这样的分割线,即从上到下只向着第一列方向拐弯或不拐弯

想象每一行都有一个挡板,为这一行A与B集合的分界线,那么把这些挡板连起来就是整张图的分界线(看图). 为了保证合法,从上到下的挡板的位置必须不能比上一行挡板位置靠右.

(为了方便,现在只讨论形如上图的分割线,即从上到下只背着第一列方向拐弯或不拐弯)

那么当两行挡板位置相等时,如果第一行挡板右边元素使可以接受的,那么就可以放心地把他加入A集合了.

因为此时由于第二行的挡板不能逾越第一行挡板的位置,如果第一行不动,他将不能再动,即使右边的元素可以接受.

即已经枚举完了一定要加入A集合的元素.

当然,当第二行右边的元素已经不可接受,第一行就可以不用等到第二行挡板和第一行一样时再移动.

考虑一个小问题

当遇到一个可以接受的元素k时,是否加入A集合,是否会因为加入A集合导致B集合出现问题?

• 当k为未加入元素的极值时,加入A集合就会缩小未来的B集合的极差.
• 当k不为未加入元素的极值时,加入A集合不会对B集合有任何影响.

算法实现

二分最小的可接受的极值上限,不断地从上到下,在保证从上到下的挡板的位置必须不能比上一行挡板位置靠右的条件下尝试移动该行的挡板.

为了保证下一行没有阻挡的情况下仅当两行挡板位置相同时才能延伸挡板,每次移动只能移动一格.(有点难说,这个意思自己理解一下稍微有点难).

当一行遇到阻碍时,因为每一次都只移动一格,该行之下的所有行要么已经被不可接受的元素阻挡,要么被这一行阻挡,所以下一次循环时就可以不用考虑改行之下的挡板.

当第一行遇到阻碍时,循环结束.统计剩下的元素组成的B集合的极值,如果可以接受,下调上限,否则

就可以返回false上调上限了??

别忘了,这只是一种情况,一共8种情况呢.(四个延伸起始方向,两个拐弯方向)

这个可以通过旋转图像后再进行二分简单的实现,但是我当初敲代码的时候少了块脑子写了4个judge,给8种情况都写了一段来判断,反正过了也就不改了.

代码

#include <iostream>
#include <cstdio>
#define INF 2147483647
using namespace std;
int a[2005][2005];
int s[2005];
int N,M;
void _getnum(int &xx)
{
 char tt=getchar();
 while(tt<'0'||tt>'9')tt=getchar();
 for(xx=0;tt>='0'&&tt<='9';tt=getchar())xx=xx*10+int(tt-'0');
}

int judge_1(int m)
{
	int minx = 1000000001,maxx = 0;
	while(1)
	{
		bool t = 0;
		for(int i = 1;i <= N;i++)
		{
			if(s[i] < s[i-1] && s[i] < M && a[i][s[i]+1] - minx <= m && maxx - a[i][s[i]+1] <= m)
			{
				s[i]++;
				t = 1;
				
				if(a[i][s[i]] < minx)minx = a[i][s[i]];
				if(a[i][s[i]] > maxx)maxx = a[i][s[i]];
			}
		}
		if(t == 0)
		{
			break;
		}
	}
	minx = 1000000001,maxx = 0;
	for(int i = 1;i <= N;i++)
	{
		for(int j = s[i] + 1;j <= M;j++)
		{
			if(a[i][j] - minx > m || maxx - a[i][j] > m)
			{
				return false;
			}
			if(a[i][j] > maxx)maxx = a[i][j];
			if(a[i][j] < minx)minx = a[i][j];
		}
	}
	return true;
}
int judge_2(int m)
{
	int minx = 1000000001,maxx = 0;
	while(1)
	{
		bool t = 0;
		for(int i = N;i >= 1;i--)
		{
			if(s[i] < s[i+1] && s[i] < M && a[i][s[i]+1] - minx <= m && maxx - a[i][s[i]+1] <= m)
			{
				s[i]++;
				t = 1;
				
			if(a[i][s[i]] < minx)minx = a[i][s[i]];
			if(a[i][s[i]] > maxx)maxx = a[i][s[i]];
			}
		}
		if(t == 0)
		{
			break;
		}
	}
	minx = 1000000001,maxx = 0;
	for(int i = 1;i <= N;i++)
	{
		for(int j = s[i] + 1;j <= M;j++)
		{
			if((minx != INF && maxx != -INF) && (a[i][j] - minx > m || maxx - a[i][j] > m))
			{
				return false;
			}
			if(a[i][j] > maxx)maxx = a[i][j];
			if(a[i][j] < minx)minx = a[i][j];
		}
	}
	return true;
}
int judge_3(int m)
{
	int minx = 1000000001,maxx = 0;
	//cout << minx << endl;
	while(1)
	{
		bool t = 0;
		for(int i = M;i >= 1;i--)
		{
			if(s[i] < s[i+1] && s[i] < N && a[s[i] + 1][i] - minx <= m && maxx - a[s[i] + 1][i] <= m)
			{
				s[i]++;
				t = 1;
				
			if(a[s[i]][i] < minx)minx = a[s[i]][i];
			if(a[s[i]][i] > maxx)maxx = a[s[i]][i];
			}
		}
		if(t == 0)
		{
			break;
		}
	}
	minx = 1000000001,maxx = 0;
	for(int i = 1;i <= M;i++)
	{
		for(int j = s[i] + 1;j <= N;j++)
		{
			if((minx != INF && maxx != -INF) && (a[j][i] - minx > m || maxx - a[j][i] > m))
			{
				return false;
			}
			if(a[j][i] > maxx)maxx = a[j][i];
			if(a[j][i] < minx)minx = a[j][i];
		}
	}
	return true;
}
int judge_4(int m)
{
	int minx = 1000000001,maxx = 0;
	while(1)
	{
		bool t = 0;
		for(int i = 1;i <= M;i++)
		{
			if(s[i] < s[i-1] && s[i] < N && a[s[i] + 1][i] - minx <= m && maxx - a[s[i] + 1][i] <= m)
			{
				s[i]++;
				t = 1;
				
			if(a[s[i]][i] < minx)minx = a[s[i]][i];
			if(a[s[i]][i] > maxx)maxx = a[s[i]][i];
			}
		}
		if(t == 0)
		{
			
			break;
		}
	}
	minx = 1000000001,maxx = 0;
	
	for(int i = 1;i <= M;i++)
	{
		for(int j = s[i] + 1;j <= N;j++)
		{
			if((a[j][i] - minx > m || maxx - a[j][i] > m))
			{
				return false;
			}
			if(a[j][i] > maxx)maxx = a[j][i];
				if(a[j][i] < minx)minx = a[j][i];
		}
	}
	return true;
}
int judge(int m)
{
	for(int i = 0;i < 2005;i++)
	{
		s[i] = 0;
	}
	s[0] = INF;
	if(judge_1(m))return true;
	for(int i = 0;i < 2005;i++)
	{
		s[i] = 0;
	}
	s[N+1] = INF;
	if(judge_2(m))return true;
	
	for(int i = 0;i < 2005;i++)
	{
		s[i] = 0;
	}
	s[M+1] = INF;
	if(judge_3(m))return true;
	
	for(int i = 0;i < 2005;i++)
	{
		s[i] = 0;
	}
	s[0] = INF;
	if(judge_4(m))return true;
	return false;
}
int main()
{
	_getnum(N);
	_getnum(M);
	for(int i = 1;i <= N;i++)
	{
		for(int j = 1;j <= M;j++)
		{
			_getnum(a[i][j]);
		}
	}
	int l = 0,r = 1000000004;
	while(l+1 < r)
	{
		int mid = (l+r+1)/2;
		if(judge(mid))
		{
			r = mid;
		}else{
			l = mid;
		}
	}
	if(!judge(l)) l=r;
	printf("%d",l);
}