题解 | #汐汐买小龙包#

B

最优成本计算

给定一个数组，需要将所有元素"连接"起来，有两种操作方式：

• 方式A：成本 = 差值 × A（按差值付费）
• 方式B：成本 = B（固定费用 目标是以最小总成本连接所有元素。 第一步：排序

sort(v.begin(), v.end());

将数组排序，这样相邻元素的差值最小，为后续计算做准备。

第二步：计算最小成本

long long ans = min(v[0]*A, B);  // 处理第一个元素
for(int i=1; i<n; i++) 
    ans += min((v[i]-v[i-1])*A, B);  // 处理后续间隔

逻辑解释：

• 第一个元素：从0位置连接到第一个元素 v[0]
  • 方式A：成本 = v[0] × A（假设从0开始）
  • 方式B：成本 = B（固定费用
• 后续间隔：连接相邻元素 v[i-1] 和 v[i]
  • 方式A：成本 = (v[i] - v[i-1]) × A
  • 方式B：成本 = B 对于每个间隔，独立选择更便宜的连接方式：
• 如果间隔很小，使用方式A（按差值付费）更划算
• 如果间隔很大，使用方式B（固定费用）更划算

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; long long A,B;
    cin>>n>>A>>B;
    vector<long long> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    sort(v.begin(),v.end());
    long long ans=min(v[0]*A,B);
    for(int i=1;i<n;i++) ans+=min((v[i]-v[i-1])*A,B);
    cout<<ans;
}