[经典面试题][腾讯]选择原料工厂(最短距离问题)

题目

12个工厂分布在一条东西向高速公路的两侧，工厂距离公路最西端的距离分别是0、4、5、10、12、18、27、30、31、38、39、47。在这12个工厂中选取3个原料供应厂，使得剩余工厂到最近的原料供应厂距离之和最短，问应该选哪三个厂 ？

来源

腾讯 盛大

思路

（1）这是一维问题，不是二维，，可以抽象成：有12个点分布在一维坐标轴上，选择3个点，使得剩余的点到最近的点的距离之和最小。

（2）工厂距离是从小到大排序的。

（3）从n个工厂中选择1个原料厂，选择位于中位数位置的工厂，距离之和最短。

（4）设A[i][j]表示从前i个工厂选择j个原料厂的最短距离。（1<=i<=j<=N） B[i][j]表示从第i个工厂到第j个工厂选择1个原料厂的最短距离。（1<=j<=i<=N）

从前i个工厂选择j个原料厂，可分为两部分：从前k个工厂选择j-1个原料厂和从第k+1个工厂到第i个工厂选择1个原料厂（1<=j-1<=k< i, k+1<=i）

所以，递归解为：

A[i][j] = B[1][i], 即j=1时

A[i][j] = min{ A[k][j-1] + B[k+1][i] }，其中1<=j-1<=k< i, k+1<=i

代码

/*———————————————* 日期：2015-03-02* 作者：SJF0115* 题目: 选择原料工厂(最短距离问题)* 来源：腾讯 盛大* 博客：———————————————–*/;int fac[100][100];// n工厂个数 count原料厂个数 result原料厂下标集合vector<int> BestFactoryPoint(int n,int count){vector<int> result;//[1,n]int k;for(int i = 1;i <= n;){//[1,n]分成两部分[1,k]有count-1个原料厂[k+1,n]有1个原料厂k = fac[n][count–];// [k+1,n]有一个原料厂,中位点就是原料厂点result.push_back(k+1 + (n-k-1)/2);// 所有原料厂寻找完毕if(count == 0){break;}(k <= count){for(int i = 1;i <= k;++i){result.push_back(i);}//forbreak;}//if// 求[1,k]部分n = k;}//forreturn result;}// 从[start,end]选择一点使其到其他点的距离最小int MinDistanceOneFactory(int point[],int start,int end){if(start > end){return -1;}//ifint mid = (start + end) / 2;// 计算距离int distance = 0;for(int i = start;i <= end;++i){distance += abs(point[i] – point[mid]);}//forreturn distance;}//int MinDistance(int point[],int n,int count){if(n <= 0){return -1;}B[n+1][n+1];// 计算第i个工厂到第j个工厂设1个原料厂的最短距离for(int i = 1;i <= n;++i){for(int j = i;j <= n;++j){B[i][j] = MinDistanceOneFactory(point,i,j);}//for}A[n+1][n+1];// i前i个工厂for(int i = 1;i <= n;++i){// 设j个原料厂// j = 1时A[i][1] = B[1][i];for(int j = 2;j <= i;++j){A[i][j] = INT_MAX;for(int k = j-1;k < i;++k){int curMin = A[k][j-1] + B[k+1][i];if(curMin < A[i][j]){A[i][j] = curMin;fac[i][j] = k;}//if}//for}//for}//forreturn A[n][count];}int main() {int array[] = {0, 0, 4, 5, 10, 12, 18, 27, 30, 31, 38, 39, 47};int n = 12;int count = 3;cout<<“最小距离->”<<MinDistance(array,n,count)<<endl;vector<int> result = BestFactoryPoint(n,count);for(int i = result.size()-1;i >= 0;–i){cout<<array[result[i]]<<” “;}//forcout<<endl;return 0;}

尝到你和你在一起的快乐，你是唯一能让我尝到酸甜苦辣的人。