營業額統計

傳送門
這個題...裸題啊,裸的不能再裸了

按天數插入,每次插入之后,比較和前驅后繼的差,取 min 統計入答案即可

注意之前已經插入過的值就不需要插入了.然后這題就 A 了

Code:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <map>
#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 ;
}