0w1

CFR 3 D. Least Cost Bracket Sequence ( Greedy )

Problem - D - Codeforces

題意:
給一個序列,有 '(', ')', '?' 三種符號,每個 '?' 有相應的代價可以轉換成左括弧或右括弧,求最小總代價,使得變成合法的括弧序列,或者判斷不存在合法的方案。

資料規模:
序列長度 1 ≤ N ≤ 5e4
轉換代價 1 ≤ A[ i ], B[ i ] ≤ 1e6
時間限制:500 ms
空間限制:64 MB

解法:
顯然不能 DP。考慮貪婪法。由左到右掃描,如果某個時機左括弧總數量小於右括弧的數量,那麼必須要把在這之前可改的右括弧變成左括弧。但任意時機右括弧少於左括弧沒關係。因此考慮先把所有 '?' 轉換成右括弧,有左到右掃描,如果左括弧數量小於右括弧數量,將可改成左括弧中代價最小的改掉。利用優先佇列水一波就可以。

時間 / 空間複雜度:
O( N lg N ) / O( N )

string seq;
vi A, B;

vi qid;

void init(){
  cin >> seq;
  for( int i = 0; i < seq.size(); ++i ){
    if( seq[ i ] == '?' ){
      qid.emplace_back( i );
    }
  }
  A = B = vi( seq.size() );
  for( int i = 0; i < qid.size(); ++i ){
    int a, b; cin >> a >> b;
    A[ qid[ i ] ] = a;
    B[ qid[ i ] ] = b;
  }
}

ll ans = 0;

void preprocess(){
  vi r2l_cost( seq.size(), INF );
  for( int i = 0; i < seq.size(); ++i ){
    if( seq[ i ] != '?' ) continue;
    seq[ i ] = ')';
    ans += B[ i ];
    r2l_cost[ i ] = A[ i ] - B[ i ];
  }
  priority_queue< pii, vp, greater< pii > > minheap;
  for( int i = 0, lcnt = 0; i < seq.size(); ++i ){
    if( seq[ i ] == '(' ){
      ++lcnt;
    } else{
      --lcnt;
    }
    if( r2l_cost[ i ] != INF ){
      minheap.emplace( r2l_cost[ i ], i );
    }
    if( lcnt < 0 ){
      if( minheap.empty() ){
        cout << -1 << endl;
        exit( 0 );
      }
      int c, id; tie( c, id ) = minheap.top(); minheap.pop();
      seq[ id ] = '(';
      ans += c;
      lcnt += 2;
    }
    if( i + 1 == seq.size() and lcnt ){
      cout << -1 << endl;
      exit( 0 );
    }
  }
}

void solve(){
  cout << ans << endl;
  cout << seq << endl;
}