HDU 2236 矩陣不同行列尋找 最小最大數的內插補點 最小 二分比對+二分枚舉區間

題意：

從矩陣每行中找一個數( 沒有2個數在同一列 )  使得找出來的數中最大值和最小值差 最小， 輸出內插補點

首先設矩陣中最小的數是 vmin , 最大的數是 vmax， 則答案一定 [0, vmax - vmin]

顯然找出來的數一定在 區間 [ 0 + x, 0 + ans + x ] ( x為合法值)

枚舉x，如果能找到比對出的結果 都是在這個區間上，說明這個區間合法 => 這個ans合法,

二分至ans ，再判斷，注意二分的上下

#include<stdio.h>
#include<string.h>

#define max Max
#define min Min

#define N 105
int map[N][N], n, vmin, vmax;
int lie[N], vis[N], p,  max, min, mid;
bool match(int x){
	for(int  i = 1; i <= n; i++)
	{
		if(vis[i])continue;
		if(map[x][i] > p + mid || map[x][i] < p)continue;
		vis[i] = 1;
		if( !lie[i] || match(lie[i])){
			lie[i] = x;
			return true;
		}
	}
	return false;
}

bool solve(){
	memset(lie,  0, sizeof(lie ));

	for(int i = 1; i <= n; i++)
	{
		memset(vis, 0, sizeof(vis));
		if( !match(i) )return false;
	}
	return true;
}
int main(){
	int T, i, j; scanf("%d",&T);
	while(T--){
		vmin = 100;
		vmax = 0;
		scanf("%d",&n);
		for(i = 1; i <= n; i++)
			for(j = 1; j <= n; j++)
			{
				scanf("%d",&map[i][j]);
				if(vmin > map[i][j]) vmin = map[i][j];
				if(vmax < map[i][j]) vmax = map[i][j];
			}
			min = 0, max = vmax - vmin;
			while( 1 )
			{
				bool ok = false;
				mid = (min + max) >>1 ;
			for(p = vmin; p + mid <= vmax ; p++)
				{
					if(solve()) { ok = true; break; }
				}
				if( ok )//如果存在一個比對使得所有數在區間 [p, p+mid] 
				{
					max = mid; 
				}
				if(min == mid)break;
				if(!ok ) min = mid;
			}
			printf("%d\n",max); //結果區間是在[0+x, 0+max +x]
	}
	return 0;
}
/*
99
1
1

2
1 2
3 4


3
1 2 3
4 5 6
7 8 9

3
9 7 8
6 4 2
1 5 3

ans:
0
1
4
3

*/