CF1984C1 题解

ikunTLE · 2024-06-14 22:05:10 · 题解

题目传送门

思路

题目中有两个选项：

1. 如果选择第一个选项，就要使两个数和最大，就是使 c 最大。

2. 如果选择第二个选项，如果 c 的值很大，那么与第一个选项没有区别，所以就要使 c 最小。

贪心思路比较简单，就是维护每次操作后的最大值和最小值。最后的最大值即为所求。

注意事项

• 不开 long long 见祖宗。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define llabs(x) (long long)(abs(x))
const int N=2e5+10;
int t,n,a[N];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        long long max_c=0,min_c=0;
        for(int i=1;i<=n;++i){
            long long maxx=max_c+a[i],minn=min_c+a[i];
            max_c=max(max(maxx,llabs(maxx)),max(minn,llabs(minn)));
            min_c=min(min(minn,llabs(minn)),min(maxx,llabs(maxx)));
        }
        printf("%lld\n",max_c);
    }
    return 0;
}