【题解】P10412 钟声远带斜阳

题目大意

给定一个长度为 $n$ 的序列 $a$ ，花费不同代价进行一下若干操作：

选择其中一个元素 $a_i$ （ $0 \le i \lt n$ ）增加一，花费 $p$ 的代价。
选择其中一个元素 $a_i$ （ $0 \le i \lt n$ ）删除，花费 $q$ 的代价（序列长度不可为 $0$ ）。
选择其中两个元素 $a_i,a_j$ （ $0 \le i \lt j \lt n$ ）进行交换，花费 $r$ 的代价。

最小化代价，使得 $\exists k_0(0 \le k_0 \lt n)$ ，将子序列 $a_0 \sim a_{k_0 - 1}$ 拼接在原序列后端，当前序列任意前缀和非负。

Solution

定义 $sum$ 表示整个序列元素之和，不难看出，对于任意一个序列，若 $sum \ge 0$ ，必然至少存在一个 $k_0$ 使得前缀非负，得到充分性。

而如果已知存在一个解 $k_0$ 使得现有序列非负，则这个序列的 sum 的值必然非负，得到必然性。

$sum \ge 0 \iff \exists k_0$

因此问题就转化成了：通过操作使得序列元素和非负。

操作三由于只能改变序列顺序，无法改变元素大小，对结果没有贡献，忽略即可。

而对于剩下的两种操作，可以采取贪心的思想，将序列元素从小到大的顺序依次删除跟新答案。

int main()
{
    cin >> n >> p >> q >> r;
    for (int i = 0; i < n; i ++)
        cin >> a[i], sum += a[i];
        
    if (sum >= 0) cout << 0 << '\n', exit(0);
    
    ans = -sum * p;
    sort(a, a + n);
    for (int i = 0; i < n; i ++)
        pre[i] = pre[i - 1] + a[i];
    
    for (int i = 0; i < n - 1; i ++)
        ans = min(ans, (i + 1) * q + max(0LL, pre[i] - sum) * p);
    
    cout << ans << '\n';
    
    return 0;
}