本文共 2583 字，大约阅读时间需要 8 分钟。
按天数插入,每次插入之后,比较和前驱后继的差,取 min 统计入答案即可
注意之前已经插入过的值就不需要插入了.然后这题就 A 了
Code:
#include #include #include #include #include #include #define Drt pair < Treap * , Treap * >#define siz(rt) ( rt == NULL ? 0 : rt->size )using std::pair ;using std::map ;const int INF = 1061109567 ;map < int , bool > mk ;int n , ans , xx ;struct Treap { Treap * son[2] ; int val , size , rank ; Treap ( int val ) : val ( val ) { son[0] = son[1] = NULL ; size = 1 ; rank = rand () ; } inline void maintain () { this->size = 1 ; if ( this->son[0] != NULL ) this->size += this->son[0]->size ; if ( this->son[1] != NULL ) this->size += this->son[1]->size ; return ; }} * root = NULL ;inline Drt Split ( Treap * rt , int k ) { if ( rt == NULL ) return Drt ( NULL , NULL ) ; Drt t ; if ( k <= siz ( rt->son[0] ) ) { t = Split ( rt->son[0] , k ) ; rt->son[0] = t.second ; rt->maintain () ; t.second = rt ; } else { t = Split ( rt->son[1] , k - siz ( rt->son[0] ) - 1 ) ; rt->son[1] = t.first ; rt->maintain () ; t.first = rt ; } return t ;}inline Treap * merge ( Treap * x , Treap * y ) { if ( x == NULL ) return y ; if ( y == NULL ) return x ; if ( x->rank < y->rank ) { x->son[1] = merge ( x->son[1] , y ) ; x->maintain () ; return x ; } else { y->son[0] = merge ( x , y->son[0] ) ; y->maintain () ; return y ; }}inline int Getrank ( Treap * rt , int key ) { if ( rt == NULL ) return 0 ; if ( key <= rt->val ) return Getrank ( rt->son[0] , key ) ; else return Getrank ( rt->son[1] , key ) + siz ( rt->son[0] ) + 1 ;}inline int Getkth ( Treap * & rt , int key ) { Drt x = Split ( rt , key - 1 ) ; Drt y = Split ( x.second , 1 ) ; Treap * node = y.first ; rt = merge ( x.first , merge ( node , y.second ) ) ; return node == NULL ? 0 : node->val ;}inline void insert ( Treap * & rt , int key ) { int k = Getrank ( rt , key ) ; Drt t = Split ( rt , k ) ; Treap * node = new Treap ( key ) ; rt = merge ( t.first , merge ( node , t.second ) ) ; return ;}int main () { scanf ("%d" , & n ) ; scanf ("%d" , & xx ) ; n -- ; ans = xx ; mk[xx] = true ; insert ( root , xx ) ; while ( n -- ) { scanf ("%d" , & xx ) ; if ( mk[xx] ) continue ; mk[xx] = true ; insert ( root , xx ) ; int a = abs ( Getkth ( root , Getrank ( root , xx ) ) - xx ) ; int b = abs ( Getkth ( root , Getrank ( root , xx + 1 ) + 1 ) - xx ) ; if ( a == 0 ) a = INF ; if ( b == 0 ) b = INF ; ans += std::min ( a , b ) ; } printf ("%d\n" , ans ) ; system ("pause") ; return 0 ;}
转载于:https://www.cnblogs.com/Equinox-Flower/p/10785273.html