洛谷P3933 Chtholly Nota Seniorious 【二分 + 贪心 + 矩阵旋转】

时间：2022-02-20 16:30:38

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

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

要求如下：

  1. 圣剑的所有护符，恰好都属于两部分中的一部分。

  2. 每个部分内部的方块之间，可以通过上下左右相互到达，而且每个内部的方块之间互相到达，最多允许拐一次弯。

例如

ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＡＡＡＡＡ

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

ＡＢＢＢＡ　　ＢＢＡＡＡ　　ＡＡＡＢＢ

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

ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＢＢＢＢＢ

　　(1)　　　　　(2)　　　　　(3)　　　　　　

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

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

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

输入输出格式

输入格式：

第一行两个自然数n,mn,mn,m

接下来nnn行，每行mmm个自然数Ai,jA_{i,j}Ai,j​表示权值

输出格式：

一个整数表示答案。

输入输出样例

输入样例#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 ≤10\le 10≤10 ≤10\le 10≤10
#3-4 1 ≤2000\le 2000≤2000
#5-7 ≤200\le 200≤200 ≤200\le 200≤200
#8-10 ≤2000\le 2000≤2000 ≤2000\le 2000≤2000

对于所有的权值1≤Ai,j≤1091\le A_{i,j} \le 10^91≤Ai,j​≤109

题解

看到最大最小还是要考虑二分呐。。。虽然本蒟蒻尝试了想二分然而并不知道怎么check
首先我们二分差值
check的思路非常妙，由题我们知道我们选出来的A是在每一行的长度是单调且连续的，由于A和B可以互换，我们不妨设最大极值在A中，那么A这样一个梯状的区域的顶角处于某个角落，我们不妨设为左上角，然后将矩阵做3次旋转就可以考虑到所有情况。

好了现在A的顶点在左上角，我们要判定条件是否成立。
首先最大值和最小值一定不在一起，
我们不妨设最大值在A中，那么我们从第一行开始找到第一个与最大值差值在check范围内的位置p
在第二行不超过p的位置同样找一个这样的边界，
这样子我们就将矩阵划分为了两个区域：
左边区域一定满足条件，因为是我们枚举出来的，那么我们再判断右区域满不满足【与最小值的差值在条件范围内】
就搞定啦~

【get 二分特性 + 矩阵旋转 + 最大值最小值划分思想】

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

using namespace std;

const int maxn = 2017,maxm = 100005,INF = 2000000000;

inline int read(){

	int out = 0,flag = 1;char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}

	return out * flag;

}

int n,m,A[4][maxn][maxn],gmax = -INF,gmin = INF;

void init(){

	n = read();

	m = read();

	int x = 1,x1 = 1,x2 = n,x3 = m,y = 1,y1 = n,y2 = m,y3 = 1,t;

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

		for (int j = 1; j <= m; j++){

			t = A[0][x][y++] = A[1][x1++][y1] = A[2][x2][y2--] = A[3][x3--][y3] = read();

			if (t > gmax) gmax = t;

			if (t < gmin) gmin = t;

		}

		x++; y = 1;

		y1--; x1 = 1;

		x2--; y2 = m;

		y3++; x3 = m;

	}

}

int endi[maxn];

bool Check(int u,int d){

	if (u & 1) swap(n,m);

	endi[0] = m;

	for (int i = 1,j; i <= n; i++){

		for (j = 1; j <= endi[i - 1]; j++)

			if (gmax - A[u][i][j] > d)

				break;

		endi[i] = j - 1;

	}

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

		for (int j = endi[i] + 1; j <= m; j++)

			if (A[u][i][j] - gmin > d){

				if (u & 1) swap(n,m);

				return false;

			}

	}

	if (u & 1) swap(n,m);

	return true;

}

bool check(int d){

	if (Check(0,d)) return true;

	if (Check(1,d)) return true;

	if (Check(2,d)) return true;

	if (Check(3,d)) return true;

	return false;

}

void solve(){

	int l = 0,r = gmax - gmin;

	while (l < r){

		int mid = (l + r) >> 1;

		if (check(mid)) r = mid;

		else l = mid + 1;

	}

	cout<<l<<endl;

}

int main()

{

	init();

	solve();

	return 0;

}


相关文章