The presidential election in Republic of Democratia is carried out through multiple stages as follows. There are exactly two presidential candidates. At the first stage, eligible voters go to the polls of his/her electoral district. The winner of the district is the candidate who takes a majority of the votes.
木として考える．葉にその区画に勝つための最小の値， を入れる．子の数の半分，小さい順に取っていく．最後に根の値が最小値になっているはず．
子の階層から小さい順に取りたいので，priority_queueを利用した．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
priority_queue < ll , vector < ll > , greater < ll > > que [ 100005 ];
int main () {
int n ;
cin >> n ;
rep ( q , n ) {
rep ( i , 100005 ) {
while ( que [ i ]. size ()) que [ i ]. pop ();
}
string s ;
cin >> s ;
int dep = 0 ;
rep ( i , s . size ()) {
if ( s [ i ] == '[' ) {
if ( s [ i + 1 ] == '[' ) {
dep ++ ;
} else {
stringstream ss ;
REP ( j , i + 1 , s . size ()) {
if ( '0' <= s [ j ] && s [ j ] <= '9' ) {
ss << s [ j ];
i ++ ;
} else {
i ++ ;
break ;
}
}
ll x ;
ss >> x ;
x = x / 2 + 1 ;
que [ dep ]. push ( x );
}
} else if ( s [ i ] == ']' ) {
int m = que [ dep ]. size ();
ll sum = 0 ;
rep ( j , m / 2 + 1 ) {
sum += que [ dep ]. top ();
que [ dep ]. pop ();
}
que [ dep - 1 ]. push ( sum );
while ( que [ dep ]. size ()) {
que [ dep ]. pop ();
}
dep -- ;
}
}
cout << que [ 0 ]. top () << endl ;
}
return 0 ;
}
