P10412 の 题解

· · 题解

通过观察不难发现 k_0 \in \left[0,n-1\right] 时的对答案没有影响。原因是不管从那个起点开始所有数的总和都是不变的。所以我们可以将原问题等价于在给定序列上进行操作使得最终的和非负。

注意到问题的答案仅于该数列所有元素的和有关，因此操作三无效。因此考虑枚举操作二的次数确定操作一的次数来更新答案。

具体的，记序列元素总和为 tot 可以对原序列排序,贪心地枚举删除最小的 i 个数，记它们的和为 sum。则操作一的次数j=\max(0,sum-tot)。此方案的答案即为 i \times q + j \times p。所有方案的最小值即为所求。

注

  1. 虽然答案在 long long 范围内，但是单个方案的大小可能超过 long long 的表示范围。

  2. 操作二最多使用 n-1 次，不能将数列删空。

code

// Created by cyx in 2024
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
using namespace std;
const int N=1e5+5;
int n,p,q,r;
int a[N];
__int128 sum;
signed main() {
    IOS;
    cin>>n>>p>>q>>r;
    for(int i=1; i<=n; i++)
        cin>>a[i],sum+=a[i];
    if(sum>=0) cout<<0,exit(0);
    sort(a+1,a+1+n);
    __int128 ans=1e18;
    for(__int128 i=0; i<=n-1; i++) {
        sum-=a[i];
        if(sum<0) ans=min(ans,(-sum)*p+1ll*i*q);
        else {
            ans=min(ans,i*q);
            break;
        }
    }
    cout<<(long long)(ans);
    return 0;
}
/*
*/