P10412 钟声远带斜阳 题解

· · 题解

记住，当你一筹莫展的时候，真诚的贪心永远是必杀技！！！

题意

给定 n 个数，进行任意次操作，使得从任意位置开始，无限循环该数列，前缀和始终为非负数。

思路

首先，目标是前缀和始终为非负数，那一定有一个位置前缀和是最小的。所以只需要让那个前缀和最小的位置非负就可以了。又因为可以从任意位置开始循环该数列，所以我们总有办法让情况尽量有利，所以经过感性思考发现：操作三没用！

然后考虑贪心。先说结论：让整个数列和最小即可。

对于这个无穷数列，前缀和最小的位置就是最小的那个数的位置。因为可以从任意位置开始，所以可以让最小的那个数排在最后。它的前缀和也就是整个数列所有数的和。

代码实现

排序，从最小的数开始尝试操作，直到数列和为非负数为止。

#include <bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
ll n,m,u,v,w,ans,cnt,num;
ll a[N];
int main(){
    cin>>n>>u>>v>>w;
    if(v%u==0)num=v/u;
    else num=v/u+1;
    //num表示执行+1操作num次及以上时选择删除操作更优 
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        cnt+=a[i]; //cnt记录数列和
    }
    sort(a+1,a+n+1); //排序，优先处理更小(代价更大)的数 

    for(int i=1;i<=n-1;i++){//因为不能删空，所以最大的那个数先不处理 
        if(cnt>=0)break; 
        a[i]=max(a[i],cnt);
        //当cnt=-3，但a[i]是-4时，如果执行+1操作只需要3次就可以了，所以取max 
        if(a[i]+num<=0)
            ans+=v;//需要的+1操作较多时使用删除操作 
        else 
            ans-=u*a[i];//需要的+1操作较少时使用+1操作 
        cnt-=a[i]; 
    }
    if(cnt<0)//此时处理最后一个数，如果最后一个数是负数，执行+1操作 
        ans-=u*cnt;
    cout<<ans<<endl;
   return 0;
}