1363的美食
题目背景
1363看到一个送分题，于是他宣布上不了70分就吃（）。
题目描述
然而他发现题目其实有点东西，于是他爆炸了，零分。于是他开始吃（），现在他有两个 \(n × m\) 的矩阵状的（） \(A\) 和 \(B\)，他可以进行若干次食用。每次食用他可以使 \(A\) 或 \(B\) 的某一行或者某一列的所有元素增加 \(1\)。但是他有强迫症，虽然他很能吃，但是必须看到 \(A\)、\(B\) 相等才肯一口闷。
于是小D很头疼，他想问问你按上述规则，至少要吃多少次，才能使 \(A\) 和 \(B\) 相等。
输入格式
第一行一个正整数 \(T\)，表示数据组数。
每组数据的第一行两个正整数 \(n\), \(m\)。
接下来 \(n\) 行，每行 \(m\) 个非负整数 \(A_{i,j}\)，表示矩阵 \(A\)。
接下来 \(n\) 行，每行 \(m\) 个非负整数 \(B_{i,j}\)，表示矩阵 \(B\)。
输出格式
对于每组数据，输出一行一个整数表示答案。如果无论怎么吃都不能使得 \(A\) 和 \(B\) 相等，输出 \(−1\)。
样例 #1
样例输入 #1
1
3 3
1 1 1
1 1 1
1 1 1
3 2 2
2 1 1
2 1 1
样例输出 #1
2
提示
对于 10% 的数据，\(n\times m\le 5\)
对于 30% 的数据，\(n\times m\le100\)
对于 60% 的数据，\(n\times m\le 10^4\)
对于 100% 的数据，\(n,m,n\times m\le 10^5\)，\(1\le T\le 5\)，\(A_{i,j},B_{i,j}\le 10^9\)
题解
美食（大嘘）
通过审题，我们知道\(1363\)需要事先处理\(a,b\)两个矩阵。为了方便料理，我们可以先处理出一个\(d\)矩阵，各个位置的元素对应地，有\(d=a-b\).因为对于\(a\)来说，\(b\)某元素加1就相当于\(a\)中对应位置的元素减1.所以，我们就只需要通过使\(d\)矩阵的某一行或某一列的元素加1或减1，来满足\(1363\)挑剔的胃。最终若是能将\(d\)矩阵的每个元素都变成\(0\)，则说明矩阵\(a=b\).
现在我们来想想，一个什么样的\(d\)矩阵才能入得了\(1363\)的法眼？不妨以下面的矩阵为例。
考虑如下策略：先固定矩阵的第\(1\)行（即不作加减处理），然后对于下面的第\(2~n\)行，我们想办法给每一行加上或减去一个数，使得该行能和第\(1\)行对应相等。
处理后就变成这种样式：
接着再考虑每一列，这时我们会发现每一列上的数都是一样的。所以我们只需要让每一列都减去对应位置第一行的数就可以将\(d\)矩阵清零。
然后就变成了一群漂亮的\(0\).
请注意，以上都是建立在\(d\)矩阵是可以被料理成\(1363\)满意的样式的基础上的。同时，若这种方法行得通，则这将是一种最“稳妥”的方法。“稳妥”的含义是，若这种方法都无法使\(1363\)满足，则再无别的方法满足他了，应当输出\(-1\).
考虑什么情况下\(1363\)注定无法被满足。
回顾一下之前的第一步（就是固定第一行的那个），倘若我们要将矩阵\(d\)的每一行都彼此相等，那么矩阵\(d\)每行间就应该具有“等差性”。
如何理解“等差性”？举个例子，如果第\(1\)行的第\(1\)个数和第\(2\)个数的差为\(n\)，那么第\(2~n\)行的第\(1\)个数和第\(2\)个数的差都应该为\(n\)，其它位置也应该满足此性质。如果有任何位置不满足，就直接输出\(-1\).
如此以来，我们要么输出\(-1\)走人，要么就得到一种最“稳妥”的方案。接下来的工作就是得到最优的方案。
通过上文的定义，我们知道：
\(Ans=\sum_{i=1}^{n} \left | x_i \right | +\sum_{j=1}^{m} \left | y_j \right |\)
(其中，\(x={0,-1,-2},y={-1,-2,-3}\))
我们的目的是使\(Ans\)尽可能地小。现考虑对\(x\)数组中每个元素加上一个数\(D\)，相应地，\(y\)数组中每个元素减去一个数\(D\).这样下来原矩阵依然是可以满足\(1363\)的，那\(Ans\)会有变化吗？上文举的例子不咋好，因为“稳妥”方案就是最优方案，我们来看下面的例子。
上图红字展示的就是一种“稳妥”的策略，我们可以通过上述的方法来优化它。
可以将\(y+D,x-D\)从而得到以下策略：
这就是一个最优的策略。
那么如何得到这个\(D\)呢？再举几个例子，不难发现\(D\)与\(Ans\)的大小关系是一个单峰函数。即是说，对于最优的\(D\)，无论\(D+1\)还是\(D-1\)都会使\(Ans\)更劣。那么，我们就可以选择三分法处理这个问题。
三分法
应用场景
二分法使用的场景是单调函数，也就是一次函数；三分法使用的场景是单峰函数，也就是二次函数。
算法实现
首先，我们需要两个点将全域(\(left~right\))分为三段。
midl=left+(right-left)/3;
midr=right-(right-left)/3;
如果\(midl\)比\(midr\)更加靠近最优解，令\(right=midr-1\)(舍弃远离的那一段)
如果\(midr\)比\(midl\)更加靠近最优解，令\(left=midl+1\)(舍弃远离的那一段)
具体到这道题，我们判断最优解的依据就是\(Ans\)的大小。
这样，每一轮迭代都会把查找范围限制在原来的\(2/3\)，直到最终逼近最优解。
AC代码（各部分代码功能见注释）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=100005;
const int inf=2147483600;
int t;
int n,m;
int x[N],y[N];
int minn(int a,int b)
{
return a<b?a:b;
}
int maxx(int a,int b)
{
return a>b?a:b;
}
int abss(int k)
{
return k>0?k:-k;
}
int check(int k)//判断midl和midr孰离最优解近
{
int res=0;
for(int i=1;i<=m;i++) res+=abss(y[i]-k);
for(int i=1;i<=n;i++) res+=abss(x[i]+k);
return res;
}
int tri_s(int l,int r)//三分！
{
while(l<r)
{
int midl=l+(r-l)/3;
int midr=r-(r-l)/3;
if(check(midl)>check(midr)) l=midl+1;
else r=midr-1;
}
return check(l);
}
signed main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int a[n+5][m+5],b[n+5][m+5],d[n+5][m+5];
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(d,0,sizeof(d));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++)//处理出d矩阵
for(int j=1;j<=m;j++)
d[i][j]=a[i][j]-b[i][j];
for(int i=1;i<=m;i++)//处理出y数组
y[i]=d[1][i];
bool flag=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++)
{
if(d[i][j]-d[i][j+1]!=d[1][j]-d[1][j+1])//出现不满足“等差性”
{
puts("-1");//直接输出-1跑路
flag=1;
break;
}
}
x[i]=d[i][1]-d[1][1];
if(flag) break;
}
if(flag) continue;
printf("%lld\n",tri_s(-inf,inf));//在全域范围内三分找D
}
return 0;
}
原文地址：http://www.cnblogs.com/fish4174/p/16787083.html
