今天做了一下谷歌2014年校招B轮的第二题，一开始我想找出一种时间复杂度最小的解法，但是后来发现我的解法还存在问题，并不总是能够得到最短路径。最后参考了当时成功提交答案的一位同学的解法，不过他的解法就是遍历所有的点，这样效率太低。希望有兴趣的大神一起探讨，找出效率最高的解法，并能与我联系，小弟感激不尽。
首先给出题目：
英文版：
Problem
Little Sin livesin a Manhattan-grid city, a 2D plane where people can only go north, west,south or east along the grid. The distance from (x1, y1) to (x2, y2) is |x1 -x2| + |y1 - y2|.
Little Sin really likes to party and is hoping to host a house party inManhattan this Sunday. Little Sin has collected a list of people who willattend, and now needs to decide at whose home she will host the party.
Little Sininvited all of the people in several rectangular areas, and all of those peoplehave said yes. A rectangular area is denoted as (x1, y1, x2, y2), where x1 ≤x2, y1 ≤ y2. People who live in a rectangular area fill all integral pointsinside it. So there are a total of (x2 - x1 + 1) * (y2 - y1 + 1) people in therectangular area (x1, y1, x2, y2).
Little Sin knowsthe coordinates of those rectangular areas. She wants the party to be hosted atthe home of one of the people who is attending, but she also doesn‘t wanteveryone else to have to travel very far: she wants to minimize the sum of alldistances from all attendees‘ houses to the party. Can you help her?
Input
The first lineof the input gives the number of test cases, T. T test cases follow. Each test casestarts with a line containing a single integer: the number of rectangularareas, B. Blines follow. Each line contains 4integers: x1, y1, x2, y2, denoting the coordinates of a rectangular area ofpeople Little Sin has invited to her party.
Output
For each testcase, output one line containing "Case #t: x y d", where t is thecase number (starting from 1) and (x, y) is the coordinates of the person whosehome the party should be hosted. If there are multiple positions with the sameminimum total distance, choose the one with the smallest x. If there are stillmultiple positions, choose the one with the smallest y. The value d is the sumof the distances from all attendees‘ houses to the point (x, y).
Limits
1 ≤ T ≤ 10.
|x1|, |y1|, |x2|, |y2| ≤ 109.
x1 ≤ x2, y1 ≤ y2.
The rectangular areas within a test case don‘t intersect.
Small dataset
1 ≤ B ≤ 100.
1 ≤ Total number of people in each testcase ≤ 1000.
Large dataset
1 ≤ B ≤ 1000.
1 ≤ Total number of people in each testcase ≤ 1000000.
Sample
input
2
1
0 0 2 2
3
-1 2 -1 2
0 0 0 0
1 3 1 3
output
Case #1: 1 1 12
Case #1:-1 2 6
考虑到很多人不习惯看英文，我就把它翻译成了中文，可能不十分准确，但是能理解意思就行了。
中文版：
Sin居住在曼哈顿市区，是一个二维平面，只能在网格里沿东西南北四个方向行走，A(x1, y1)和B (x2, y2) 两点间的距离是 |x1 -x2| + |y1 - y2|。
Sin喜欢参加派对，她希望这个周日在曼哈顿举行一场家庭派对。她已经收集了参加派对人员的名单。现在她要决定在哪个家里举行派对。
Sin邀请了几个矩形区域的所有人，所有人都说参加。矩形区域用（x1,y1,x2,y2)表示，x1 ≤ x2,y1 ≤ y2. 矩形区域里面的所有整数点都住了人。所以在矩形区域(x1, y1, x2, y2)里一共有(x2 - x1+ 1) * (y2 - y1+ 1) 个人。
Sin知道这些矩形区域的坐标，她想在参加派对的其中一人家里举行这个party，但是她不想其他人跑得太远，她想使所有参加派对的人走的总距离最短。你能帮她吗？
输入：
第一行是总的测试用例数T，接着是T个测试用例。每个测试用例的第一行是一个整数B，B表示矩形区域的个数，紧接着是B行，每行包括四个整数x1,y1, x2, y2，表示Sin邀请的矩形区域的人的坐标。
输出：
对每个测试用例，输出一行，格式为：Case#t: x y d，其中t是测试用例的序号（从1开始），（x,y)是party举行的位置坐标，如果出现有多个点有相同的最短路径，则输出x坐标最小的那个。如果还有多个点，则输出y坐标最小的。d是所有参加派对的人住的地方到点(x, y)的距离之和。
限制：
1 ≤ T ≤10.
|x1|, |y1|, |x2|, |y2| ≤ 109.
x1 ≤ x2, y1 ≤ y2.
所有矩形区域不重叠
小数据集
1 ≤ B ≤100.
1 ≤ 每个测试用例中参加派对的总人数 ≤ 1000.
大数据集
1 ≤ B ≤1000.
1 ≤ 每个测试用例中参加派对的总人数 ≤ 1000000.
首先说说我的想法：先分别求出n个矩形的中心c1(x1,y1)、c2(x2,y2)...cn(xn,yn)，然后求出c1、c2...cn的最小外接矩形D，再求出D的中心O，再在c1、c2...cn中找出与中心O距离最短的点cx，再在cx所在的矩形中找出距离cx最近的点h（h可能和cx重合，也可能不重合）。点h即为举办party的位置，其他所有点到该点的距离之和最短。
代码如下：
#include <iostream>
#include <math.h>
using namespace std;
//求一个数组中最大值的函数
float maxf(const float a[],int len)
{
float temp = -1e9;
for(int i = 0;i < len;i++)
{
if(a[i] > temp)
temp = a[i];
}
return temp;
}
//求一个数组中最小值的函数
float minf(const float a[],int len)
{
float temp = 1e9;
for(int i = 0;i < len;i++)
{
if(a[i] < temp)
temp = a[i];
}
return temp;
}
//计算一个点到其他所有点的街区距离之和
int sumDist(float x[],float y[],int x1[],int x2[],int y1[],int y2[],int cx,int cy,int len)
{
int re;
float sum = 0.0;
for (int i = 0;i < len;i++)
{
if(fabs(x[i] - cx) < 1 || fabs(y[i] - cy) < 1)
continue;
int num = (x2[i] - x1[i] + 1)*(y2[i] - y1[i] + 1);
sum += (fabs(x[i] - cx) + fabs(y[i] - cy))*num;
}
re = static_cast<int>(sum);
return re;
}
//求四个数中的最小值
float min4(float x1,float x2,float x3,float x4)
{
float r1 = min(x1,x2);
float r2 = min(x3,x4);
if(r1 < r2)
return r1;
else
return r2;
}
int main()
{
int T;
cin>>T;
int result_x[10];
int result_y[10];
int MinDistance[10];
memset(result_x,0,sizeof(result_x));
memset(result_y,0,sizeof(result_y));
memset(MinDistance,0,sizeof(MinDistance));
int i = 0;
for (i = 0;i < T;i++)
{
int rectNum = 0;
cin>>rectNum;//矩形的个数
int *x1 = new int[rectNum];
int *y1 = new int[rectNum];
int *x2 = new int[rectNum];
int *y2 = new int[rectNum];
float *centerX = new float[rectNum];
float *centerY = new float[rectNum];
for(int k = 0;k < rectNum;k++)
{
cin>>x1[k]>>y1[k]>>x2[k]>>y2[k];
centerX[k] = (float)(x1[k] + x2[k])/2.0;
centerY[k] = (float)(y1[k] + y2[k])/2.0;
}
float minX,minY,maxX,maxY;
float cx,cy;
minX = minf(centerX,rectNum);
minY = minf(centerY,rectNum);
maxX = maxf(centerX,rectNum);
maxY = maxf(centerY,rectNum);
cx = (minX + maxX)/2.0;
cy = (minY + maxY)/2.0;
int index = 0;
float minDis = 1e9;
//找出与所有点距离之和最短的中心点
for (int j = 0;j < rectNum;j++)
{
if((fabs(centerX[j]-cx) + fabs(centerY[j] - cy)) < minDis)
{
minDis = fabs(centerX[j]-cx) + fabs(centerY[j] - cy);
index = j;
}
}
int sum = 0;
int c = 0;
if((x1[index] + x2[index]) % 2 == 0 && (y1[index] + y2[index]) % 2 == 0)
{
result_x[i] = (x2[index] + x1[index])/2;
result_y[i] = (y2[index] + y1[index])/2;
int dx = (x2[index] - x1[index])/2;
int dy = (y2[index] - y1[index])/2;
c = dx*(1 + dx)*(y2[index] - y1[index] + 1) + dy*(1 + dy)*(x2[index] - x1[index] + 1);
sum = sumDist(centerX,centerY,x1,x2,y1,y2,result_x[i],result_y[i],rectNum);
MinDistance[i] = sum + c;
}
else if((x2[index] + x1[index]) % 2 == 0 && (y2[index] + y1[index]) % 2 != 0)
{
result_x[i] = (x2[index] + x1[index])/2;
int ty1 = (y2[index] + y1[index] - 1)/2;
int ty2 = (y2[index] + y1[index] + 1)/2;
float s1 = fabs((float)ty1 - cy);
float s2 = fabs((float)ty2 - cy);
if(s1 < s2)
result_y[i] = ty1;
else
result_y[i] = ty2;
int dx = (x2[index] - x1[index])/2;
int dy = (y2[index] - y1[index])/2;
sum = sumDist(centerX,centerY,x1,x2,y1,y2,result_x[i],result_y[i],rectNum);
c = dx * (1 + dx) * (y2[index] - y1[index] + 1) + (dy*(1+dy) + dy + 1) * (x2[index] - x1[index] + 1);
MinDistance[i] = sum + c;
}
else if((x2[index] + x1[index]) % 2 != 0 && (y2[index] + y1[index]) % 2 == 0)
{
result_y[i] = (y2[index] + y1[index])/2;
int tx1 = (x2[index] + x1[index] - 1)/2;
int tx2 = (x2[index] + x1[index] + 1)/2;
float s1 = fabs((float)tx1 - cx);
float s2 = fabs((float)tx2 - cx);
if(s1 < s2)
result_x[i] = tx1;
else
result_x[i] = tx2;
int dx = (x2[index] - x1[index])/2;
int dy = (y2[index] - y1[index])/2;
sum = sumDist(centerX,centerY,x1,x2,y1,y2,result_x[i],result_y[i],rectNum);
c = dy * (1 + dy) * (x2[index] - x1[index] + 1) + (dx*(1+dx) + dx + 1) * (y2[index] - y1[index] + 1);
MinDistance[i] = sum + c;
}
else
{
int tx1 = (x2[index] + x1[index] - 1)/2;
int tx2 = (x2[index] + x1[index] + 1)/2;
int ty1 = (y2[index] + y1[index] - 1)/2;
int ty2 = (y2[index] + y1[index] + 1)/2;
float s1 = fabs((float)tx1 - cx) + fabs((float)ty1 - cy);
float s2 = fabs((float)tx1 - cx) + fabs((double)ty2 - cy);
float s3 = fabs((float)tx2 - cx) + fabs((double)ty1 - cy);
float s4 = fabs((float)tx2 - cx) + fabs((double)ty2 - cy);
float r = min4(s1,s2,s3,s4);
if(r == s1)
{
result_x[i] = tx1;
result_y[i] = ty1;
}
else if(r == s2)
{
result_x[i] = tx1;
result_y[i] = ty2;
}
else if(r == s3)
{
result_x[i] = tx2;
result_y[i] = ty1;
}
else
{
result_x[i] = tx2;
result_y[i] = ty2;
}
int dx = (x2[index] - x1[index])/2;
int dy = (y2[index] - y1[index])/2;
sum = sumDist(centerX,centerY,x1,x2,y1,y2,result_x[i],result_y[i],rectNum);
c = (dx*(1+dx) + dx + 1) * (y2[index] - y1[index] + 1) + (dy*(1+dy) + dy + 1) * (x2[index] - x1[index] + 1);
MinDistance[i] = sum + c;
}
delete x1;
delete y1;
delete x2;
delete y2;
delete centerX;
delete centerY;
}
for (i = 0;i < T;i++)
{
cout<<"Case #"<<i+1<<":"<<result_x[i]<<" "<<result_y[i]<<" "<<MinDistance[i]<<endl;
}
}
在调试的过程中，发现这个解法在某些情况下得不到正确答案。
例如输入为：
1
3
-3 1 -1 3
2 0 6 3
-2 -5 1 -2
输出结果为（0，-3） 265，但是正确答案为（2,1） 217，所以我的解法必须再改进。
在谷歌招聘官网上看了一个学生的答案，他是遍历所有的点，找出最短距离，代码如下：
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
vector<pair<int, int> > v;
vector<int> x, y;
vector<long long> sumx, sumy;
for (int i = 0; i < n; ++i) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
for (int tx = x1; tx <= x2; ++tx) {
for (int ty = y1; ty <= y2; ++ty) {
v.push_back(make_pair(tx, ty));
x.push_back(tx);
y.push_back(ty);
}
}
}
n = v.size();
sort(v.begin(), v.end());
sort(x.begin(), x.end());
sort(y.begin(), y.end());
sumx.push_back(0);
sumy.push_back(0);
for (int i = 0; i < n; ++i) {
sumx.push_back(sumx.back() + x[i]);
sumy.push_back(sumy.back() + y[i]);
}
pair<int, int> ans;
long long bestcost = 1ll << 61;
for (int i = 0; i < n; ++i) {
int tx = lower_bound(x.begin(), x.end(), v[i].first) - x.begin(), ty = lower_bound(y.begin(), y.end(), v[i].second) - y.begin();
long long cost = (long long)v[i].first * (tx + 1) - sumx[tx + 1]
+ sumx.back() - sumx[tx + 1] - (long long)v[i].first * (n - 1 - tx)
+ (long long)v[i].second * (ty + 1) - sumy[ty + 1]
+ sumy.back() - sumy[ty + 1] - (long long)v[i].second * (n - 1 - ty);
if (cost < bestcost) {
bestcost = cost;
ans = v[i];
}
}
static int id = 0;
cout << "Case #" << ++id << ": " << ans.first << ‘ ‘ << ans.second << ‘ ‘ << bestcost << endl;
}
return 0;
}
这种方法效率太低，我想一定有时间复杂度更小的算法，只是我现在还没想好。有兴趣的可以研究一下，欢迎交流。谷歌2014年中国区校园招聘B轮题目二（求N个矩形内的所有点到其中一点的街区距离之和最短）解法探讨与代码实现（C++）,布布扣,bubuko.com