题目
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
代码
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <math.h>
using namespace std;
int fac[100][100];
vector<int> BestFactoryPoint(int n,int count){
vector<int> result;
int k;
for(int i = 1;i <= n;){
k = fac[n][count--];
result.push_back(k+1 + (n-k-1)/2);
if(count == 0){
break;
}
if(k <= count){
for(int i = 1;i <= k;++i){
result.push_back(i);
}
break;
}
n = k;
}
return result;
}
int MinDistanceOneFactory(int point[],int start,int end){
if(start > end){
return -1;
}
int mid = (start + end) / 2;
int distance = 0;
for(int i = start;i <= end;++i){
distance += abs(point[i] - point[mid]);
}
return distance;
}
int MinDistance(int point[],int n,int count){
if(n <= 0){
return -1;
}
int B[n+1][n+1];
for(int i = 1;i <= n;++i){
for(int j = i;j <= n;++j){
B[i][j] = MinDistanceOneFactory(point,i,j);
}
}
int A[n+1][n+1];
for(int i = 1;i <= n;++i){
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;
}
}
}
}
return 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]]<<" ";
}
cout<<endl;
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
阿里面试20题 百度面试10题 华为面试10题 京东面试13题 腾讯面试37题 头条面试10题 项目经理面试常遇问题 经典面试题 程序员 IT经理 项目经理 面试题 研发经理 高级程序员 经典面试题
71道Android经典面试题
腾讯面试题 前端面试题 腾讯的前端面试题。
出现几率最高和覆盖范围最广的一套经典Java面试题.docx 最新Java编程面试题全集(共50道题+答案).docx 遇到的一些Java面试题回顾.docx 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++...
最新腾讯PHP面试题1. php 的垃圾回收机制 PHP 可以自动进行内存管理,清除不需要的对象。 PHP 使用了引用计数 (reference counting) GC 机制。 每个对象都内含一个引用计数器 refcount,每个 reference 连接到对象,...
腾讯校园招聘历年经典面试题汇总:前端岗!
腾讯Java面试题
腾讯java面试题 2013年腾讯java笔记题,
腾讯系统工程师面试题 腾讯系统工程师面试题 腾讯系统工程师面试题
腾讯php面试题解析
10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题
腾讯面试题解析,android面试题,2020年面试题,网络基础,常用三方库,算法基础等等的。腾讯面试题解析,android面试题,2020年面试题,网络基础,常用三方库,算法基础等等的
在这里汇总了腾讯历年的笔试面试题,希望对和我一样正在找工作的朋友一点帮助
企业-腾讯校招面试题真题(20题)-新增
主要是华为 腾讯的面试题 和一些面试技巧
腾讯面试题及面试经历(技术工程师类), 应聘的技术支持类。
(腾讯)后台开发面试题解答
腾讯的经典校招面试笔试题,是你走进腾讯的很好资料。
腾讯近年来笔试面试题合集 包括校园招聘与实习生招聘 主要是技术类
汇总的腾讯的笔试面试题,还包括了实习招聘等。