题解：B4103 [CSP-X2023 山东] 代价

· · 题解

题目简述

有 n 件产品，规格分别为 a_{1} \sim a_{n}，需要把所有产品的规格改成相同的。

操作 A：将 a_{i} 的规格改成 a_{i+1}，代价为 A。
操作 B：将 a_{i} 的规格改成 a_{i-1}，代价为 B。

求把所有产品的规格改成相同的需要的最小代价。

主要思路

比较简单，先将 a 排一遍序，然后遍历 a_{1} \sim a_{n}，记录一个最小值表示答案。每次让 a_{1} \sim a_{i-1} 的产品规格改成 a_{i}，代价为：

[a_{i} \times (i-1) - \sum_{j=1}^{i-1} a_{j}] \times A

让 a_{i+1} \sim a_{n} 的产品规格改成 a_{i}，代价为：

[\sum_{j=i+1}^{n} a_{j} - a_{i} \times (n-i)] \times B

求和的过程可以用前缀和解决，最后将答案设为答案和这两个代价的总和中的最小值即可，依次遍历，就可以得到最后的答案。

最最后：十年 OI 一场空，___。

AC Code

#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define endl '\n'
typedef long long ll;
const int N = 1e5 + 10;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef unsigned long long ull;
// ----------------------------

// ----------------------------
ll pre[N];
ll nums[N];
// ----------------------------
inline ll read() {
    ll f=1,sum=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
    return sum*f;
}

void print(ll x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9){print(x/10);}
    putchar(char(x%10+'0'));
}

int main() {
    ll n = read();
    ll a = read();
    ll b = read();
    for (int i=1;i<=n;i++) nums[i] = read();
    // ------------------------
    ll ans = 1e18;
    sort(nums+1,nums+n+1);
    for (int i=1;i<=n;i++) pre[i] = pre[i-1] + nums[i];
    for (int i=1;i<=n;i++) {
        ll sum1 = (nums[i]*(i-1)-pre[i-1]) * a;
        ll sum2 = ((pre[n]-pre[i])-nums[i]*(n-i)) * b;
        ans = min(ans,sum1+sum2);
    }
    // ------------------------
    print(ans);
    return 0;
}