Codeforces 257D


题意略。

思路:这个题目最重要的是那个不等式 a[i] <= a[i+1] <= 2 * a[i]  ,你会发现0 <= a[i+1]  -  a[i] <= a[i],令x = a[i+1] - a[i],那么对于a[i-1]来说,

当x = 0时,abs(x - a[i-1])== a[i - 1];当x = a[i]时,abs(x - a[i - 1])== a[i - 1]。也就是说,abs(x - a[i - 1]) <= a[i - 1]。

从n到1来遍历,我们总是令x = abs(x - a[i - 1]),到最后,0 <= abs(x - a[1]) <= a[1]也就自然满足了。

当x >= a[i - 1]时,我们应该在a[i - 1]前加 '-';反之,我们应该在x前加 '-'。

这个加'-'的过程,我开始是用树状数组区间修改点查询做的,后来发现TLE。由于加 '-' 是对后面整体和个体加的,我们可以开两个数组,一个记录单点,

一个记录整体,到时候遍历就可以达到O(n)的复杂度了。

详见代码:

#include<bits/stdc++.h>
#define maxn 100050
using namespace std;
typedef long long LL;

LL a[maxn];
int mark[maxn],t[maxn],n;

int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    LL x = a[n] - a[n - 1];
    mark[n - 1] = -1;
    for(int i = n - 2;i >= 1;--i){
        if(x < a[i]){
            x = a[i] - x;
            t[i + 1] = 1;
        }
        else{
            x -= a[i];
            mark[i] = -1;
        }
    }
    int sum = 0;
    for(int i = 1;i <= n;++i){
        int temp;
        sum += t[i];
        temp = sum + mark[i];
        if(temp < 0) temp = 1;
        printf("%c",(temp & 1) ? '-' : '+');
    }
    printf("\n");
    return 0;
}