D - Left Right Operation

思路：

1、求前缀和

2、从后往前遍历，把某个后缀都变为R，记录最多让数组和减小多少

3、从前往后遍历，把某个前缀都变为L，记录最小答案（前i个变为L，后面的n-i个数让减小最多的后缀变为R）

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N,L,R;cin>>N>>L>>R;
    vector<ll> A(N);
    for(int i=0;i<N;i++) cin>>A[i];
    vector<ll> sum(N+1),ma(N+1);
    for(int i=1;i<=N;i++){
        sum[i]=sum[i-1]+A[i-1];
    }
    for(int i=N-1;i>=0;i--){
        ma[i]=(sum[N]-sum[i])-R*(N-i);
        ma[i]=max(ma[i],ma[i+1]);
    }
    
    ll ans=(1LL<<61);
    
    ll l=0;
    
    for(int i=0;i<=N;i++){
        ans=min(ans,l+sum[N]-sum[i]-ma[i]);
        l+=L;
    }
    
    cout<<ans<<endl;
}

原文地址：https://blog.csdn.net/weixin_73550568/article/details/135724452

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！