CF1845 D. Rating System [思维题+数形结合]

传送门:CF

[前题提要]:自己在做这道题的时候思路完全想错方向,导致怎么做都做不出来,看了题解之后感觉数形结合的思考方式挺好的(或者这种做法挺典的),故写篇题解记录一下

题目很简单,不再解释.先不考虑$k$,想想是一种什么情况?很显然应该是跟下图一样是一个折线图的变化.

然后是一个很简单的事实:我们选取的K一定是前缀和的某一个值,更为准确的来说,应该是一个即将减少的一个前缀和值.这个结论自己把玩一下应该是不难发现的,简单的讲一下为什么是这样.因为对于一个即将减少的值来说,我们不妨选取这个值,因为这个值肯定比即将减少的那个值大,那为啥不选这个更大的值呢.而对于中间段的数来说,那些数只是中间值,两端点必然有一个点比它更为优秀.

那么现在随便选取一个端点作为我们的K,看看原图会发生什么情况

考虑选择的K的值为红横线.不难发现原本白色的折线因为现在K的出现需要往左上进行一个平移.
继续看蓝色的圈,我们会发现原本的平移还不够,我们需要将整个部分进行再一次平移.(因为懒所以没有进一步画出).

上面这段操作很重要,是这一道题的关键.仔细品一下上面的操作,我们就会发现后面那部分的贡献其实就是后缀最大后缀和(两个前缀和差其实就是后缀和啦),也就是当前位置开始的所有的后缀和的最大值.直接讲可能有点抽象,建议仔细看看上面的图的平移操作.数形结合一下很好理解.
PS:出现蓝圈的原因就是因为该后缀和更大.

那么这道题的解法也就呼之欲出了.考虑枚举每一个前缀和作为我们的K,然后计算一下贡献即可.

但是还存在一种特殊情况需要再仔细考虑一下:

对于上图的情况,我们会发现最后一段的后缀和贡献是负的,并且此时没办法进行平移.怎么解决?想一下平移的实际意义,不难发现应该令该贡献为0,也就是后缀最大值的初始值应该定义0

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];int rmax[maxn],sum[maxn];
signed main() {int T=read();while(T--) {int n=read();for(int i=1;i<=n;i++) {a[i]=read();}for(int i=1;i<=n;i++) {sum[i]=sum[i-1]+a[i];}rmax[n]=0;for(int i=n-1;i>=0;i--) {rmax[i]=max(rmax[i+1],sum[n]-sum[i]);}int maxx=sum[n],ans=sum[n];for(int i=0;i<n;i++) {if(sum[i]+rmax[i]>maxx) {maxx=sum[i]+rmax[i];ans=sum[i];}	}cout<<ans<<endl;}return 0;
}