1 条题解

  • 0
    @ 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%
上传者