CFR 257 D. Sum ( Recursion, Math )

Problem - 257D - Codeforces

題意：
給數列 a，滿足 a[ i ] ≤ a[ i + 1 ] ≤ 2 * a[ i ]。要求對每項定正負，使得總和介於 [ 0, a[ 0 ] ]。

資料規模：
The first line contains integer n (1 ≤ n ≤ 1e5) — the size of the array. The second line contains space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 1e9) — the original array. It is guaranteed that the condition ai ≤ ai + 1 ≤ 2·ai fulfills for any positive integer i (i < n).

解法：
考慮最後兩項，abs( a[ n - 2 ] - a[ n - 1 ] ) 一定介於 [ 0, a[ n - 2 ] ]。拿這個取代 a[ n - 2 ]，於是可以發現一直往左走，最後會有 [ 0, a[ 0 ] ]。從右邊算到左邊，左邊若是需要右邊算出的這個總和為負，那其實是要這整坨的符號翻轉。用遞迴可以很簡潔。

時間 / 空間複雜度：
O( N )

#include <bits/stdc++.h>
using namespace std;

void dfs( vector< int > &a, int &neg, int nxt, int x, string &ans ){
  if( x < 0 ){ // need positive nxt
    neg = 0;
    return;
  }
  if( a[ x ] >= nxt ){ // need positive this, negative nxt, so toggle all signs for nxt
    dfs( a, neg, a[ x ] - nxt, x - 1, ans );
    ans += "+-"[ neg ];
    neg ^= 1;
  } else{ // need negative this, positive nxt, so leave nxt as it is
    dfs( a, neg, nxt - a[ x ], x - 1, ans );
    ans += "+-"[ neg ^ 1 ];
  }
}

signed main(){
  ios::sync_with_stdio( 0 );
  int n; cin >> n;
  vector< int > a( n );
  for( int i = 0; i < n; ++i ){
    cin >> a[ i ];
  }
  string ans;
  {
    int neg;
    dfs( a, neg, 0, n - 1, ans );
  }
  cout << ans << endl;
  return 0;
}