今天在叉姐的群里找点题目做，这题目还是很好的：提意思如下

【有M个可以提供计算机网络的端口和N台计算机（计算机数量少于端口数），每个端口和计算机有一个坐标（一维的）！其中端口与计算机链接的距离 |x - y|。所求用最少的网线使每台计算机都可以链接网络。】

很容易想到网线不会交叉！所以对于折中形式就会想到  这个方程     (dp[i][j]    代表   第 i 台电脑 链接 到 前  j  个接口的最少花费)。

    dp[i][j] = min( dp[i][j-1] , dp[i-1][j-1] + abs(a[i]-b[j])  );

可是  会看到    『M (1 ≤ M ≤ 100000), N (1 ≤ N ≤ 2000, N ≤ M)』  纳尼  这怎么破！时间&&内存   QAQ

好好观察下你的  【状态转移方程】 一个状态 i，只与 状态 i-1  有关 所以 数组就不用开成  dp[N][M]   相对应的  

dp[2][M]   就 可以了！

同学不要着急 啊 ！  时间仔细 想想 时间也是可以优化的!!!

对于 M很大 而  N  却 不多的数据 上面的 会很 慢，毕竟 有点暴力！ 怎们 优化 呢！ 对于 这样的连线问题 当然 越近越好。如果你已经有了答案就不要看了取写吧 ！   （自己想到的才是最好的）。 

 

 

 

 

对于每一个电脑的位置最好用lower_bound() 找到那个位置 ！一般这个位置对于 单个计算机而言 是最近的距离，

但是当计算多了起来时就不一定是我们要的那个端口了，但是在 【P-N，P+N】 区间内一个接口对于这太计算机是最优的选择！

好好想！只要处理出 这一部分的dp 值  就可以了!

只要记录下上一个状态的的起点和终点就可以了

主要的代码就是祥下面的一样（这里面的 m,n和题目意思里面的不一样）。

 

p=lower_bound(a,a+n,b[0])-a;    int sta=0;    int s1=0,e1=m-1,s2,e2;    for(i=0; i