北语 12.6 五彩斑斓的梦想

点击查看代码

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=1e6+10;int n;
LL a[N],s[N];int main()
{cin>>n;LL sum=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);s[i]=s[i-1]+a[i];sum+=a[i];}LL del=0;for(LL d=0;d<=n-1;d++){LL t=d*(d+1);if(t>s[d+1]) del=max(del,t-s[d+1]);}sum=sum+del;cout<<sum;return 0;
}

主要是对思维的考察，理解题目含义。因为是严格递增的序列，所以如果要置换的话那么取前面的数置换的话会使得增大量最大，因此就选择前面的置换，d表示变化量，d+1表示变化的区间，d（d+1）就表示这个区间总的变化量，然后用前缀和做差即可，遍历所有的d，时间复杂度是n，可以接受