codeforces1038D.Slime(思维)

题目链接:codeforces1038D. Slime

题意:n个slime,每个slime有一个自己的体积,每个slime可以吃与自己相邻的slime,体积为x的slime吃了体积为y的slime之后的体积为x-y,问最后可能的最大体积。

题解:

对于3个slime,假定体积为x,y,z,1)若y先吃x得y-x,然后z吃掉y,体积为z-y+x。2)若y先吃z得y-z,然后x吃y得x-y+z,即为等效的。

所以我们对于n个slime先绝对值相加得sum,然后考虑以下三种情况:

1)全为正,我们就需要减去一个slime,即减去最小的一个。

2)全为负,同1)。

3)答案即为sum

注意特判n==1的特殊情况。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[500009];
ll sum,ans;
int main()
{
    scanf("%d",&n);
    int num=0;
    sum=ans=0;
    for(int i=1;    i<=n;   i++)
    {
        scanf("%lld",&a[i]);
        sum+=abs(a[i]);
        if(a[i]<0)  num++;
    }
    if(n==1)    return printf("%lld\n",a[1]),0;
    if(num==n)
    {
        for(int i=1;    i<=n;   i++)
            ans=max(ans,sum+a[i]*2);
    }
    else    if(num==0)
            {
                for(int i=1;    i<=n;   i++)
                    ans=max(ans,sum-a[i]*2);
            }
    else    ans=sum;
    printf("%lld\n",ans);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。