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 = ;i <= n;++i) scanf("%lld",&a[i]);

    LL x = a[n] - a[n - ];

    mark[n - ] = -;

    for(int i = n - ;i >= ;--i){

        if(x < a[i]){

            x = a[i] - x;

            t[i + ] = ;

        }

        else{

            x -= a[i];

            mark[i] = -;

        }

    }

    int sum = ;

    for(int i = ;i <= n;++i){

        int temp;

        sum += t[i];

        temp = sum + mark[i];

        if(temp < ) temp = ;

        printf("%c",(temp & ) ? '-' : '+');

    }

    printf("\n");

    return ;

}

巴特西

Codeforces 257D

最新文章

热门文章