# 题目描述

你和 De 在一个月前突然消失，被困在了 “完美世界” 中。

​你们获得了一个数组 $a_0,a_1,⋯,a_{n−1}$，需要用最少的代价将它完美化。

​定义一个数组是完美的，当且仅当：

​将此数组依次复制连接无穷次得到数组 $b$：$b_0,b_1,⋯,b_{n−1},b_n,⋯$ 其中 $b_i=a_{i \, \mathrm {mod} \, n}$，且存在位置 $k_0≥0$ 使得 $∀k≥k_0,\sum_{i = k_0}^k bi≥0$。

​你们可以对数组进行任意次以下操作：

• 花费 $p$，选择一个 $0≤i<n$，对其值增加一；

• 花费 $q$，选择一个位置 $0≤i<n$，删除该位置的数，同时更新数组长度，数组不能删空；

• 花费 $r$，交换数组中的两个位置 $0≤i<j<n$ 上的数。

# 输入格式

第一行 $4$ 个整数，第一个 $n$，后接三个数 $p,q,r$ 分别表示数组大小以及三种操作代价。

保证 $1≤n≤10^5$，$1≤p,q,r≤10^9$。

第二行 $n$ 个整数，表示数组，其中 $|ai|≤10^9$,$0≤i<n$。

# 输出格式

一行，一个整数，表示将数组完美化的最小代价。

# 输入样例

5 1 2 5

2 -2 3 -3 -1

# 输出样例

1

# 题解：排序 + 贪心

考虑到当数组之和小于 $0$ 时，这个数组肯定是不完美的。但如果数组之和不小于 $0$ 呢？我们来尝试证明一下数组一定是完美的。

我们考虑处理出 $b$ 的前缀和数组 $sum$，这个数组一定存在一个最小值，设为 $sum_k$（这是因为 $a$ 数组总和不小于 $0$，因此 $sum$ 一定有下界）。如果我们起点设为 $a_{k + 1}$，那么从 $a_{k + 1}$ 起的一段和（设到 $a_t$ 为止）都是 $sum_t - sum_k$，这个数一定是 $\ge 0$ 的。

因此，问题转化成：通过三种操作，使得数组总和不小于 $0$。

这个时候我们就发现操作三实际上是无意义的操作了，考虑前两个操作，对于第二个操作，删掉正数显然对我们有害，我们要尽可能删掉最小的负数，所以我们枚举要删除几个负数，剩下的全部由第一个操作处理。注意数组 不能删空。

有一个细节：如果我们从 $0$ 开始枚举删除数量，那么全由第 $1$ 个操作算出的花费会超过 long long 的表示范围。如果从 $n - 1$ 开始枚举删除数量，那么就不会超过 long long 的表示范围，同时我们发现，随着删除数字的增多，第二个操作会越来越不划算，直到某一点之后不如第一个操作划算，也就是说，花费关于删除个数的函数是 单峰 的，所以我们从后往前枚举删除个数，一旦花费不再减少，就直接 break 掉循环，这样我们计算过程中就一定不会爆 long long 。

时间复杂度：由于需要排序，所以复杂度为 $O(n \log n)$。

参考代码：

#include <stdio.h>

#include <stdlib.h>

typedef long long ll;

int n, p, q, r, negCnt, a[100010];

ll sum, negSum, cost = 2e18;

int Cmp(const void *a, const void *b)

{

    return *(int*)a - *(int*)b;

}

ll max(ll a, ll b)

{

    return (a > b) ? a : b;

}

int main()

{

    // freopen("S.in", "r", stdin);

    // freopen("S.out", "w", stdout);

    scanf("%d%d%d%d", &n, &p, &q, &r);

    for (int i = 1; i <= n; ++ i)

    {

        scanf("%d", &a[i]);

        sum += a[i];

    }

    qsort(a + 1, n, sizeof(a[1]), Cmp);

    for (int i = 1; i < n && a[i] < 0; ++ i)

    {

        ++ negCnt;

        negSum -= a[i];

    }

    for (int i = negCnt; ~i; -- i)

    {

        ll t = 1ll * i * q + max(0, -sum - negSum) * p;

        if (t > cost)

            break;

        cost = t;

        negSum += a[i];

    }

    printf("%lld\n", cost);

    return 0;

}