自动搬运

查看原文

来自洛谷，原作者为

	wylnh 漫山遍野你的脸庞，唯有遗忘是最漫长

搬运于2025-08-24 22:52:26，当前版本为作者最后更新于2023-11-16 22:44:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

做法：模拟

题意：一个长为 $n$ 的环形数组，每次操作对于任意 $i,j$，删除 $a_j$，将 $a_i$ 减去 $a_j$，使得最后剩余的数最大。

思路：由题意可知，一次操作即将两数合并为两数之差。因此假设按操作先后顺序， $a_1$ 表示最后一个操作的数， $a_n$ 表示第一个操作的数，题意即为将 $a_1$ 到 $a_n$ 连成一个算式，在每个数之前添加一个符号，使得算式值最大。

• 对于第 $i$ 个数，若想让其符号为 $+$，则需将其与第 $i-1$ 个数做一次操作，否则直接操作。
• 比如想构造 $a_1-a_2-a_3+a_4+a_5$，则：
  • 先从前往后找第一个符号为 $+$ 的数，即 $a_4$，那么就将其与 $a_3$ 做一次操作，得到 $a_1,a_2,a_3-a_4,a_5$。
  • 同样找到符号为 $+$ 的 $a_5$，将其与 $a_3-a_4$ 做一次操作，得到 $a_1,a_2,a_3-a_4-a_5$。
  • 最后剩下的都是 $-$ 号了，就直接依次进行操作，得到 $a_1-a_2-(a_3-a_4-a_5)$，即 $a_1-a_2-a_3+a_4+a_5$。
• 所以只需要选择相邻的数，前一个为 $+$ 号，后一个为 $-$ 号，两两做差，枚举最大值即可。
• 注意：当 $n=1$ 时，直接输出 $a_1$，无需进行操作。

代码：

#include<bits/stdc++.h>
#define ll long long
#define INF -0x7f7f7f7f
using namespace std;
const int N=1e6+10;
ll T,n,a[N];
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		ll sum=0,ans=INF;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			sum+=abs(a[i]);//统计最大可能达到的值
		}
		if(n==1){//特判
			cout<<a[1]<<"\n";
			continue;
		}
		for(int i=1;i<=n;i++){
			ans=max(ans,sum-abs(a[i])-abs(a[i%n+1])+a[i]-a[i%n+1]);//sum减去两数的绝对值，加上做差后的值，即为每次操作的贡献
		}
		cout<<ans<<"\n";
	}
	
	return 0;
}

后记：如有错误或不足请 dalao 指出。（点个再走呀！）