题解：P10412 「QFOI R2」钟声远带斜阳

· · 题解

首先分析题意。

因为数列无限延长而总和恒非负。

所以这个数列总和非负。

形象地理解就是说，如果数列总和为负数，无限求和就一定会是负数，不满足题意。

而如果总和非负，从头开始无限求和也不会出现负数。

下面用数学公式表达转化后的题意。

\sum_{i = 0}^{n-1}{a_i} \ge 0

求使原式满足上面这个式子所需最小代价。

然后考虑题目给出的三种操作。

对于操作一，给哪个数加一对结果没有影响，可以最后考虑。

对于操作二，删除绝对值较大的负数有时比操作一更优。

对于操作三，交换位置事实上对结果没有影响。

因此想到用贪心解决，下面简单讲下思路。

如果原总和非负，不用操作就满足题意，答案输出零即可。

如果原总和是负数，考虑贪心解决。

首先将原数组从小到大排序，因为越小的负数，使用操作二就更优。

从前往后遍历序列。

如果用操作二更优，就用操作二。

如果用操作一更优，就用操作一把总和加到零，因为数组已经排序，后面的数用操作二不会更优。

输出总代价即可。

特别地，需要记录删除数的个数，以满足不能将数列删空的要求。

下面提供参考代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+10;
int a[MAXN],n,p,q,r,cnt,cost,sum;
signed main(){
    cin>>n>>p>>q>>r;
    for(int i=1;i<=n;i++) cin>>a[i],cnt+=a[i];
    if(cnt>=0){
        cout<<0<<'\n';
        return 0;
    }
    sort(a+1,a+1+n);
    cnt=-cnt;
    for(int i=1;i<=n;i++) if(a[i]<0){
        if(cnt<=0){
            break;
        }
        if(q<=p*min(cnt,-a[i])&&sum<n-1){
            cost+=q;
            cnt+=a[i];
            a[i]=0;
            sum++;
        }else{
            cost+=p*min(cnt,-a[i]);
            cnt-=min(cnt,-a[i]);
            a[i]+=min(cnt,-a[i]);
        }
    }
    cout<<cost<<'\n';
    return 0;
}