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 105int 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;}/*991121 23 431 2 34 5 67 8 939 7 86 4 21 5 3ans:0143*/