P9742 题解（2023 激励计划评分 9）

· · 题解

P9742 题解

题目大意

给定一个数列 c，你需要给第 i 个位置赋一个唯一排名 b_i，若 b_i>i，则将答案减去 c_i。若 b_i<i，则将答案加上 c_i，若相等，则什么都不做。求答案的最大值。

题目思路

先讨论 c_i 全部大于 0 的情况。

显然可以让第一名掉到最后一名，其他人顺次往前移一位。但这可能不是最优方案。

但是我们可以让 1 至 i 名保持不变，第 i+1 名掉到最后一名，i+2 到 n 名顺次往前移（1\le i\le n），这才是一种最优方案。

那么 c_i 全部小于 0 的情况也可以照样推出来，这里直接放结论：让 i 至 n 名保持不变，第 i-1 名升到第一名，1 到 i-2 名顺次往后移（1\le i\le n）。

现在考虑正解。

我们可以将原数列分成三部分：

第一部分：1 到 x-1，里面全是正数。

第二部分：y+1 到 n，里面全是负数。

第三部分：x 到 y，里面有正有负有 0。（1\le x\le y\le n）

对于第一、二部分，我们可以直接套用上面的结论。

对于第三部分，c_x 必然是非正数，c_y 必然是非负数。我们可以先让第 x 位空出来，接着让所有正数顺次往前移，所有非正数往后移，你会发现刚好能移完（自己画个图就能懂）。也就是这一部分累加 c_i 的绝对值即可。

参考代码

有一个细节，就是用前缀和优化，见代码：

#include<bits/stdc++.h>
#define gsum(l,r) (sum[r]-sum[l-1])
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll T,n,c[N],tmp,lft,rgt,sum[N],ans1,ans2;
int main(){
    cin>>T;
    while(T--){
        ans1=ans2=0;
        cin>>n;
        for(int i=1;i<=n;i++) scanf("%lld",&tmp);
        for(int i=1;i<=n;i++){
            scanf("%lld",c+i);
            sum[i]=sum[i-1]+abs(c[i]);
        }
        for(lft=1;c[lft]>0&&lft<=n;lft++);
        for(rgt=n;c[rgt]<0&&rgt>=1;rgt--);
        for(int i=1;i<lft;i++) ans1=max(ans1,-c[i]+gsum(i+1,lft-1));
        for(int i=n;i>rgt;i--) ans2=max(ans2,c[i]+gsum(rgt+1,i-1));
        cout<<ans1+ans2+gsum(lft,rgt)<<'\n';
    }
    return 0;
}