1 条题解
-
0XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2024-10-20 19:57:21
考虑两堆相邻但奇妙值符号相反的石子(0既可以视为正也可以视为负),无论合并时是谁减谁,新石子堆的奇妙值绝对值都等于原石子堆奇妙值绝对值之和,而谁减谁可以决定新石子堆的符号,那就不难构造一种顺序,使得每次合并都是在操作两堆奇妙值符号相反的石子,而最后一次合并奇妙值一定是一正一负,此时用正奇妙值减负奇妙值,那么最终答案就是所有奇妙值的绝对值之和。
注意一些特殊情况的处理,例如奇妙值全为正或全为负的时候,必须牺牲一部分绝对值之和,先选择一个两堆石子合并来得到一个不同的符号,此外n=1的时候又不适用于全正全负的处理,都是需要注意的点。std
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<ctime> #include<algorithm> #define MAXN 2000005 #define Abs(x) (((x)>0)?(x):(-(x))) using namespace std; inline int read() { int num=0,sgn=1; char ch=getchar(); while (ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if (ch=='-')sgn=-1,ch=getchar(); while (ch>='0'&&ch<='9')num*=10,num+=ch-'0',ch=getchar(); return num*sgn; } int T,n,s[MAXN]; int pos,neg,ans,mn; int main(){ T=read(); while (T--) { n=read(); pos=neg=ans=0; for (int i=1;i<=n;i++) { s[i]=read(); if (s[i]>=0)pos=1; if (s[i]<=0)neg=1; ans+=Abs(s[i]); } if (n==1) { printf("%d\n",s[1]); continue; } mn=ans; for (int i=2;i<=n;i++) mn=min(mn,Abs(s[i])+Abs(s[i-1])-Abs(s[i]-s[i-1])); if (pos*neg)printf("%d\n",ans); else printf("%d\n",ans-mn); } return 0; }
- 1
信息
- ID
- 1030
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 6
- 已通过
- 2
- 通过率
- 33%
- 上传者