人生艰难，不仅仅在于我们要经历成长过程中的种种磨砺，而更要经受一些迫不得已的离别之苦。于家人，为了求学、工作，我们背井离乡，从此乡人再也没能喝上一口井水。于爱人，情侣间一个简单的拥抱，都因为异地而变得更加来之不易。
但是，这一切终会有一个简单的理由支撑着我们勇往直前：为了你生命中最在乎的人而努力变好。
如果可以，请放下手中无聊、无谓、无奈、无趣的事情，对他们说句：我爱你！
而最让我眼中常含满泪水的，是我知道你们有一个算法不会。
今天小编想要给大家介绍一条脚踩技面、手撕HR、月入十万、迎娶白富美、登上人生巅峰的捷径：当当当当~——“华为软件精英挑战赛”；武汉长沙赛区因为名校众多，已经成为了最激烈的竞争赛区。来一起回顾一下之前的2017年的大赛题。
一、奖项设置
一等奖，1队，奖金￥20万、奖杯和证书；面试绿卡、实习offer等优才计划；
二等奖，2队，每队奖金￥10万、奖杯和证书；面试绿卡、实习offer等优才计划；
三等奖，5队，每队奖金￥5万、奖杯和证书；面试绿卡、实习offer等优才计划；
最优美代码奖，1队，每队奖金￥1万、奖杯和证书；面试绿卡、实习offer等优才计划；
二、比赛问题定义
背景：大视频解决方案中，视频业务体验非常关键，视频内容如何有效传送到最终消费者是决定视频体验好坏的核心环节。
本次赛题基本描述
在给定结构的G省电信网络中，为了视频内容快速低成本的传送到每个住户小区，需要在这个给定网络结构中选择一些网络节点附近放置视频内容存储服务器。需要解决的问题是：在满足所有的住户小区视频播放需求的基本前提下，如何选择视频内容存储服务器放置位置，使得成本最小。
本次赛题通用性描述
网络结构模型：给定一个由若干网络节点（例如路由器、交换机）构成的网络结构无向图，每个节点至少与另外一个节点通过网络链路相连（网络链路特指两个网络节点之间直接相连的网络通路，中间没有其他网络节点，相当于无向图中的一条边），一个节点可以将收到的数据通过网络链路传输给相连的另一个节点。每条链路的网络总带宽不同（例如某条链路的总带宽为10Gbps）。而每条链路承载的视频传输需要按照占用带宽的多少收取对应网络租用费，每条链路的单位租用费均不同（例如某条链路的租用费为1,000元/Gbps，即1K/Gbps）。某条链路上被占用的带宽总和不得超过该链路的总带宽。
消费节点：给定的网络结构中有部分网络节点直接连接到小区住户的网络，每个小区住户网络在这个给定的网络结构图中呈现为一个消费节点，不同消费节点的视频带宽消耗需求不同。
视频内容服务器：视频内容服务器存放视频内容（如：电影影片、电视剧等），视频内容服务器的视频数据流可以经由网络节点与链路构成的网络路径流向消费节点，视频内容服务器的输出能力没有上限，可以服务多个消费节点，一个消费节点也可以同时从多台视频内容服务器获取视频流。部署一台视频内容服务器需要费用成本（例如300,000元/台，即300K/台），所有服务器的成本均相同。
比赛程序内容：请你设计一个程序寻找最优的视频内容服务器部署方案：从网络结构模型中选择一部分网络节点，在其上/附近一对一的部署视频内容服务器，视频内容服务器与对应的这个节点直连，与对应的这个网络节点之间的通信没有带宽限制、也没有通信成本。提供的部署方案需要使得视频流从视频内容服务器经过一些网络节点和链路到达消费节点，并满足所有消费节点的视频带宽消耗需求。
在满足所有消费节点视频带宽消耗需求的前提下，使得耗费的总成本（视频内容服务器部署成本+带宽租用成本）最低。部署方案不仅需要包括部视频内容服务器的节点位置，而且还要包括每个消费节点与所有视频内容服务器之间的网络路径以及路径上占用的带宽。
比赛胜负规则
若给定的网络拓扑模型不存在满足条件的方案，则输出无解，程序运行时间越短者胜出。若存在满足条件的方案，则成本越低者胜出。若两个方案的成本相同，则程序运行时间越短者胜出。
比赛用例示例：
上图为G省网络拓扑图，黑色圆圈为网络节点，红色圆圈为消费节点，圆圈内的数字为节点编号。节点之间的连线为网络链路。链路上的标记(x, y)中，x表示链路总带宽（单位为Gbps），y表示每Gbps的网络租用费。消费节点相连链路上的数字为消费节点的带宽消耗需求（单位为Gbps）。
现在假设需要在该网络上部署视频内容服务器，满足所有消费节点的需求。一个成本较低的方案如下图所示，其中绿色圆圈表示已部署的视频内容服务器，通往不同消费节点的网络路径用不同颜色标识，并附带了占用带宽的大小：
但该方案的成本不一定是最低的。因此现在需要参赛者提供的程序能够针对不同的比赛用例，给出成本最低的部署方案。
与这个题目非常相近的是“基站选址”问题。
【题目分析】
一条直线上给定相对距离Di（距第一个村庄的距离）的N个村庄中建K个基站，每个村庄i接收的范围为前后Si，建基站费用Ci，一个村庄要么被接受到要么额外支付Wi。设计方案求最小总费用。
【算法分析】
朴素方程为f[i]j=MIN(f[k][j-1]+Wk+1…j).W预处理需要N3时间，DP需要N2*K的时间。显然需要优化。
其实这样一个“裸”的方程看起来似乎很难再在时间上优化下去，因为该算法的瓶颈在于预处理的“复杂”（预处理涉及到题中的C、S、W）。这时，我们就需要对方程进行改变，让其显得更加“简洁”。f[i]j=MIN(f[k][j-1]+W[k+1…j]（k+1…j中k和i都覆盖不到的村庄的W和）+Ci。Ci为常数，DP又可以滚动优化，所以方程实际上要干的事就是f[i]=MIN(f[k]+W[k+1…j])。为了计算方便，我们可以再在最后面设一个村庄n+1，k增加1，令d[n+1]=INF。那么基站数量一定下，最优解就是f[n]。
显然现在我们对于每个村庄，都可以在O(logn)的时间内二分查找出它向前向后最多能覆盖到的地方，这个预处理在后面的分析中会用到。
我们进一步分析W[k+1…j]的计算。显然一个村庄p覆盖不到的条件是同时满足Dp+Sp<Di,Dp-Sp>Dk.现在我们假设有一个k，一个i，考虑覆盖到的村庄。
我们现在假设k不变，i增大1，那么会发生什么变化？很显然，原本被k覆盖到的村庄还是被覆盖的，但被i覆盖到的村庄左边一部分没有被覆盖了，也就意味着这些村庄需要另外给付钱了！回到那个条件，我们发现这便是Di单调递增使得一些原本覆盖到的村庄p覆盖不到了！如果我们已知W[k+1…i]，怎么求出W[k+1…i+1]？很显然的，加上新增的村庄的W即可。
当然，事情还没那么简单，由于我们DP时是固定i求一个k使解最小，自然而然我们可以初步想到一个思路用线段树维护每个f[k]+W[k+1…j]的值，“新增的村庄”打个标记加上去就行。
算法流程：
1.读入，预处理每个村庄向前向后最多能覆盖到的地方记为st[i],ed[i]
2.循环j=1…k表示当前建第几个村庄
3.利用上次的f（即每个点的初值）建线段树
4.清空旧的f
5.循环i=1…n
6.查找线段树中0…i-1里f的最小值
7.最小值+Ci后赋值给f[i]
8.对于i，若ed[x]=i，则在线段树中0…st[x]-1集体加上Wx
(原因：考虑每个x（满足ed[x]=i，具体实现可用链表（数组模拟）），这样做是为 了对于i后面的村庄如果选定村庄k，且x够不到（x原本刚刚好能被i覆盖）， 那么这个k的f[k]就要加上Wx了。）
9.用当前的f[n]更新最优解
10.输出最优解
时间复杂度O(knlogn)
空间复杂度O(n)
【总结】
DP优化，突破口就是利用了Di单调递增的性质，并合理使用数据结构加以优化。
【吐槽】
算法分析第二段及之后均为看题解后总结得来。
【附程序】
#include<cstdio>
#include<cstring>
#define rep(i,x,y) for(i=x;i<=y;i++)
#define rep_(i,x,y) for(i=x;i>=y;i--)
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int INF=~0U>>2;
const int MAXN=20010;
const int MAXK=102;
typedef int arr[MAXN];
int n,k,i,j,pos,ans,min0,en0;
arr d,c,s,w,f,st,ed;
struct tree
{
int min[1<<16],en[1<<16];
void pdown(int i)
{
en[i<<1]+=en[i];min[i<<1]+=en[i];
en[(i<<1)+1]+=en[i];min[(i<<1)+1]+=en[i];
en[i]=0;
}
void pup(int i)
{
min[i]=MIN(min[i<<1],min[(i<<1)+1]);
}
void build(int i,int x,int y)
{
en[i]=0;
if(x!=y)
{
build(i<<1,x,(x+y)>>1);
build((i<<1)+1,((x+y)>>1)+1,y);
pup(i);
}
else min[i]=f[x];
}
void find(int i,int x,int y,int l,int r,int kind)
{
if(x>y)return;
if(l>y || r<x)return;
if(x>=l && y<=r)
{
switch(kind)
{
case 1: //查找最小值
min0=MIN(min0,min[i]);
break;
case 2: //加上一个值
en[i]+=en0;min[i]+=en0;
break;
}
}
else
{
pdown(i);
find(i<<1,x,(x+y)>>1,l,r,kind);
find((i<<1)+1,((x+y)>>1)+1,y,l,r,kind);
pup(i);
}
}
}a;
struct biao
{
int edge;
arr e,b,first,last,w;
void clean()
{
edge=0;
memset(first,-1,sizeof(first));
memset(b,-1,sizeof(b));
}
void add(int x,int y,int z)
{
e[edge]=y;w[edge]=z;
if(first[x]==-1)first[x]=edge;
else b[last[x]]=edge;
last[x]=edge++;
}
}q;
int findl(int x)
{
int l,r;
for(l=1,r=n;l<r;)
{
if(x<=d[(l+r)>>1])r=(l+r)>>1;
else l=((l+r)>>1)+1;
}
return l;
}
int findr(int x)
{
int l,r;
for(l=1,r=n;l<r;)
{
if(x>=d[(l+r+1)>>1])l=(l+r+1)>>1;
else r=((l+r+1)>>1)-1;
}
return l;
}
int main()
{
freopen("base.in","r",stdin);
freopen("base.out","w",stdout);
scanf("%d%d",&n,&k);
rep(i,2,n)scanf("%d",&d[i]);
rep(i,1,n)scanf("%d",&c[i]);
rep(i,1,n)scanf("%d",&s[i]);
rep(i,1,n)scanf("%d",&w[i]);
n++;d[n]=INF;k++;
q.clean();
rep(i,1,n)
{
st[i]=findl(d[i]-s[i]);
ed[i]=findr(d[i]+s[i]);
q.add(ed[i],st[i]-1,w[i]);
}
ans=INF;
f[0]=0;rep(i,1,n)f[i]=INF;
rep(j,1,k)
{
a.build(1,0,n);
f[0]=0;rep(i,1,n)f[i]=INF;
rep(i,1,n)
{
min0=INF;
a.find(1,0,n,0,i-1,1);
f[i]=min0+c[i];
for(int pos=q.first[i];pos>=0;pos=q.b[pos])
{
en0=q.w[pos];
a.find(1,0,n,0,q.e[pos],2);
}
}
ans=MIN(ans,f[n]);
}
printf("%d\n",ans);
scanf("\n");
return 0;
}
本公众号分享自己从程序员小白到经历春招秋招斩获10几个offer的面试笔试经验，其中包括【Java】、【操作系统】、【计算机网络】、【设计模式】、【数据结构与算法】、【大厂面经】、【数据库】期待你加入！！！
1.计算机网络----三次握手四次挥手
2.梦想成真-----项目自我介绍
3.你们要的设计模式来了
4.震惊！来看《这份程序员面试手册》！！！
5.一字一句教你面试“个人简介”
6.接近30场面试分享
7.你们要的免费书来了
京公网安备 11010502036488号