[CSP-X 2023 山东] 代价

知识点

比较排序、前缀和、分段线性函数

解题思路

将规格升序排序，建立前缀和。把目标设为某个已有规格v时，左侧每个规格增加到v，右侧每个规格减少到v，用前缀和O(1)求总代价。枚举所有已有规格取最小值。

正确性说明

目标小于最小规格或大于最大规格时，向中间靠近会严格减少代价，故最优目标在其间。相邻两个已有规格之间，需增加和减少的产品集合不变，代价是目标值的线性函数，最小值可在区间端点取得。因此枚举已有规格不遗漏最优解；前缀和表达式逐项累加的正是两类修改费用。

易错点

A是增加代价，B是减少代价，不能颠倒；数据范围允许规格为0；n=1或全部相同费用为0；乘法和总和最大达约10^17，使用long long。

复杂度

时间O(n log n)，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;long long A,B;cin>>n>>A>>B;vector<long long>a(n),s(n+1);for(auto&x:a)cin>>x;sort(a.begin(),a.end());for(int i=0;i<n;++i)s[i+1]=s[i]+a[i];long long ans=LLONG_MAX;for(int i=0;i<n;++i){long long left=a[i]*i-s[i],right=s[n]-s[i+1]-a[i]*(n-i-1);ans=min(ans,A*left+B*right);}cout<<ans<<'\n';}