CFR 3 D. Least Cost Bracket Sequence ( Greedy )
題意:
給一個序列,有 '(', ')', '?' 三種符號,每個 '?' 有相應的代價可以轉換成左括弧或右括弧,求最小總代價,使得變成合法的括弧序列,或者判斷不存在合法的方案。
資料規模:
序列長度 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; }