自动搬运

查看原文

来自洛谷，原作者为

	zjpwdyf 不场切绿不改个签 || 复健 OI 中

搬运于2025-08-24 22:51:22，当前版本为作者最后更新于2023-10-15 21:11:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9742 题解

题目大意

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

题目思路

• 当 $c_i>0$ 时，我们肯定希望 $i$ 的排名上升。
• 当 $c_i<0$ 时，我们肯定希望 $i$ 的排名下降。
• 当 $c_i=0$ 时，则排名任意。

先讨论 $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;
}