5938. 分离计划

Description

  众所周知，小Z拥有者足以毁灭世界的力量，可惜他不能控制这份力量，小J和小Z的关系十分亲密，一天小J预感到了小Z体内的力量将要爆发。
这次爆发的力量比以往都要强大，以至于将小Z分为了两个整体，彼此之间靠着万有引力互相靠近，一旦融合，世界将不复存在。
  为了拯救世界，小J决定打造一个容器G，将小Z的两个部分分别装在容器G的一个部分，用以控制小Z
   容器由n*m个魔法水晶组成，他们组成了一个n行m列的矩阵，每个魔法水晶都有自己的能量值，容器需要
  被分为两个部分，使得每个魔法水晶都属于且仅属于一个部分，并且任何一个魔法水晶都可以在矩阵中只经过和自己属于同一部分的魔法水晶由一条最多改变一次方向的路径抵达另一个和他处于同一部分的魔法水晶
   例如：
ＡＡＡＡＡ. .ＡＡＡＡＡ. .ＡＡＡＡＡ
ＡＡＢＡＡ. .ＢＡＡＡＡ. .ＡＡＡＢＢ
ＡＢＢＢＡ. .ＢＢＡＡＡ. .ＡＡＡＢＢ
ＡＡＢＡＡ. .ＢＡＡＡＡ. .ＡＢＢＢＢ
ＡＡＡＡＡ. .ＡＡＡＡＡ. .ＢＢＢＢＢ

.......(1).................(2)................(3).........
使用.隔开（辣鸡的题面格式化）
其中12是不合法的容器，3是合法的容器
对于每一个部分，他的不稳定性是属于这个部分的所有魔法水晶能量值的极差（最大-最小）
对于整个容器，不稳定性是两部分不稳定性中的最大值
为了知道自己能不能拯救世界，不白白浪费时间，小J想知道整个容器的最小的不稳定值

Input

第一行两个数n，m代表魔法水晶组成的矩阵大小
随后n行，每行m个整数表示魔法水晶的能量值

Output

一行一个整数，表示最小的不稳定值

Sample Input

Sample Output

11

样例说明
ＢＢＢＡ
ＢＢＢＡ
ＢＢＢＡ
ＢＡＡＡ
B极差12-1=11 A极差20-10=10，不稳定值为11，分法不唯一

做法：：二分答案，假设最大值在蓝色区域，最小值在红色区域，考虑如何检验，对于每一行找到红色区域的最大范围，再在蓝色区域中检验极差，旋转 4 遍，复杂度 n*m*log 值域，由于每次检验时都有较多剪枝，实际运行速度十分可观。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #define N 2007
  5 using namespace std;
  6 int a[N][N],b[N][N],ans=1e9;
  7 int n,m;
  8 
  9 void Init(){
 10     scanf("%d%d",&n,&m);
 11     for(int i=1;i<=n;++i)
 12         for(int j=1;j<=m;++j)
 13             scanf("%d",&a[i][j]);
 14 }
 15 
 16 inline int min(int a,int b){
 17     return a<b?a:b;
 18 }
 19 
 20 inline int max(int a,int b){
 21     return a>b?a:b;
 22 }
 23 
 24 bool check(int aim){
 25     int mi=1e9,mx=0,Mi=1e9,Mx=0;
 26     int last=m;
 27     for(int i=1;i<=n;i++){
 28         for(int j=1;j<=last;j++){
 29             int tmp1=mi,tmp2=mx;
 30             mi=min(a[i][j],mi);
 31             mx=max(a[i][j],mx);
 32             if (mx-mi>aim){
 33                 mi=tmp1;
 34                 mx=tmp2;
 35                 last=j-1;
 36                 break;
 37             }
 38         }
 39         for(int j=last+1;j<=m;j++){
 40             Mi=min(a[i][j],Mi);
 41             Mx=max(a[i][j],Mx);
 42             if (Mx-Mi>aim) return false;
 43         }
 44     }
 45     return true;
 46 }
 47 
 48 bool CHECK(int aim){
 49     int mi=1e9,mx=0,Mi=1e9,Mx=0;
 50     int last=1;
 51     for(int i=1;i<=m;i++){
 52         for(int j=n;j>=last;j--){
 53             int tmp1=mi,tmp2=mx;
 54             mi=min(a[j][i],mi);
 55             mx=max(a[j][i],mx);
 56             if (mx-mi>aim){
 57                 mi=tmp1;
 58                 mx=tmp2;
 59                 last=j+1;
 60                 break;
 61             }
 62         }
 63         for(int j=last-1;j>=1;j--){
 64             Mi=min(a[j][i],Mi);
 65             Mx=max(a[j][i],Mx);
 66             if (Mx-Mi>aim) return false;
 67         }
 68     }
 69     return true;
 70 }
 71 
 72 bool Check(int aim){
 73     int mi=1e9,mx=0,Mi=1e9,Mx=0;
 74     int last=1;
 75     for(int i=n;i>=1;i--){
 76         for(int j=m;j>=last;j--){
 77             int tmp1=mi,tmp2=mx;
 78             mi=min(a[i][j],mi);
 79             mx=max(a[i][j],mx);
 80             if (mx-mi>aim){
 81                 mi=tmp1;
 82                 mx=tmp2;
 83                 last=j+1;
 84                 break;
 85             }
 86         }
 87         for(int j=last-1;j>=1;j--){
 88             Mi=min(a[i][j],Mi);
 89             Mx=max(a[i][j],Mx);
 90             if (Mx-Mi>aim) return false;
 91         }
 92     }
 93     return true;
 94 }
 95 
 96 bool ChecK(int aim){
 97     int mi=1e9,mx=0,Mi=1e9,Mx=0;
 98     int last=n;
 99     for(int i=m;i>=1;i--){
100         for(int j=1;j<=last;j++){
101             int tmp1=mi,tmp2=mx;
102             mi=min(a[j][i],mi);
103             mx=max(a[j][i],mx);
104             if (mx-mi>aim){
105                 mi=tmp1;
106                 mx=tmp2;
107                 last=j-1;
108                 break;
109             }
110         }
111         for(int j=last+1;j<=n;j++){
112             Mi=min(a[j][i],Mi);
113             Mx=max(a[j][i],Mx);
114             if (Mx-Mi>aim) return false;
115         }
116     }
117     return true;
118 }
119 
120 void Work(){
121     int l=0,r=1e9;
122     while(l<r){
123         int mid=(l+r)/2;
124         if (check(mid)||CHECK(mid)||Check(mid)||ChecK(mid)) r=mid;
125         else l=mid+1;
126     }
127     ans=min(ans,l);
128 }
129 
130 void change(){
131     for(int i=1;i<=n;i++)
132         for(int j=m;j>=1;j--)
133             b[i][m-j+1]=a[i][j];
134     for(int i=1;i<=n;i++)
135         for(int j=1;j<=m;j++)
136             a[i][j]=b[i][j];
137 }
138 
139 int main(){
140     freopen("separate.in","r",stdin);
141     freopen("separate.out","w",stdout);
142     Init();
143     Work();
144     change();
145     Work();
146     printf("%d",ans);    
147 }

View Code