codeforces contest 257

（ACM）思维

257D Sum(思维)

题意

• $n$ 个数，满足 $a_i ≤ a_{i + 1} ≤ 2·a_i$，改变这些数的正负，使它们的和在 $0$ 和 $a_1$ 之间（包含）。

题解

• 从后往前维护一个 $now$ ，使得 $-a_{i}<=now<=a_i$
• 最后维护到 $a_1$，如果是负数的话，反一下就可以了。
• 对于每个 $i$，$now=now-a[i]$ 或者 $now=now+a[i]$ 一定能满足。
• 证明如下：
  
  • 条件一： $-a_{i+1}<=now<=a_{i+1}$
  • 条件二： $a_{i+1}-a_i<=a_i$
  • $0<=now<=a_{i+1}：$$-a_{i}<=now-a_i<=a_i$ 成立
  • $-a_{i+1}<=now<0：$$-a_{i}<=a_i-a_{i+1}<=now+a_i<a_i$ 成立
  • 综上，得证

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl
const int N=100005;
int res[N],a[N];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        ///read
        for(int i=1;i<=n;++i) scanf("%d",a+i);
        ///solve
        ll sum=a[n];res[n]=1;
        for(int i=n-1;i>=1;--i) {
            if(-a[i]<=sum+a[i]&&sum+a[i]<=a[i]) {
                sum=sum+a[i];
                res[i]=1;
            } else {
                sum=sum-a[i];
                res[i]=0;
            }
        }
        if(sum<0) {
            for(int i=1;i<=n;++i) res[i]=1-res[i];
        }
        ///print
        for(int i=1;i<=n;++i) printf("%c",res[i]?'+':'-');
        puts("");
    }
    return 0;
}