最少操作次数分析
每次操作仅能将某台服务器的负载值增加 1 或减少 1,因此想让所有服务器的负载值变为相同,总操作次数等于
其中 (X) 为目标负载值。当 (n) 为奇数时,取 (X) 为所有 (L_i) 的中位数可使该和最小。记该中位数为 (T)。
最小代价策略
每次对服务器 (i) 进行增减操作,代价等于所选连通集合内所有服务器的代价系数之和。为了使总代价最小,对服务器 (i) 的每一次操作都应选择一个包含 (i) 且总代价系数之和最小的连通集合。
给定一棵由 n 台服务器组成的树形网络,服务器编号为 1 到 n,保证 n 为奇数。每台服务器 i 有一个初始负载值 Li 和一个代价系数 Ci。
你每次操作可以选定一个连通的服务器集合(即树的一个连通子图,集合内任意两台服务器之间的简单路径上的所有服务器都在该集合中),并选择该集合中的一台服务器,将其负载值增加 1 或减少 1。此次操作的代价等于该连通集合内所有服务器的代价系数之和。
你的目标是将所有服务器的负载值变为相同。你需要首先保证总操作次数最少,在此前提下,使得总代价尽可能小(代价可以为负数)。
请计算并输出这个最小总代价。
约束条件:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册