题解 CF257D 【Sum】

123456zmy · 2020-11-02 11:50:42 · 题解

题意：
给一个数组 a，对于任意的 1\le i<n，满足 a_i\le a_{i+1}\le2a_i。

你要为其中每个数加一个符号，使得它们的和在 0 到 a_1 之间。

考虑从后往前贪心。设当前状态下 i 位及以后的数的和为 s_i，当 s_{i+1}>a_i 时，a_i 符号设为 -，否则将符号设为 + 并将 i 位以后的数符号反转。题目保证了 a_i\le a_{i+1}\le2a_i，所以 s_i 一定不大于 a_i。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100001],s,ans[100001],b[100001],tmp;
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    s=a[n];
    for(int i=n-1;i;i--)
    {
        if(s>a[i])ans[i]=1;
        else b[i+1]=1;
        s=abs(s-a[i]);
    }
    for(int i=1;i<=n;i++)tmp^=b[i],putchar(tmp^ans[i]?'-':'+');
    return 0;
}