挺有趣的一道题。。
中文题就不写题意了。乍一看像是个博弈,但是仔细分析下,可以发现,其实当先手的那个人选了某一条线段后,答案A-B-B是确定的。为什么呢?因为他们都会尽可能多的去把线段扩进去嘛。所以就是怎么求一个线段最多能扩进多少子线段了。这样的话,问题就比较简单了。先给所有的线段离散化,然后按右端点排序,这里要注意的是,在右端点相同的情况下,要把左端点小的放前面。然后一条条枚举过来了,当前线段能扩进的最大值,就是之前出现的,且左端点的值大于当前线段左端的那些,那么这个就非常easy了,弄个树状数组统计就好了,这样我们就把A求出来了。然后就是B了,这个其实也非常简单,其实就是之前所有线段里面,左端点大于当前线段的的那些线段,能获得的A的值,所以,这里再弄个树状数组维护左端点的最值就好了。
代码:
#include<stdio.h> #include<string.h> #include<algorithm> #define lowbit(x) (x&(-x)) using namespace std ; const int maxn = 111111<<1 ; struct Line { int l , r ; bool operator < ( const Line &t ) const { if ( r == t.r ) return l < t.l ; return r < t.r ; } } e[maxn] ; int x[maxn<<1] ; int c[2][maxn<<1] ; void update ( int f , int pos , int v ) { while ( pos ) { if ( f ) c[f][pos] = max ( c[f][pos] , v ) ; else c[f][pos] += v ; pos -= lowbit ( pos ) ; } } int query ( int f , int pos ) { int ret = 0 ; while ( pos < maxn ) { if ( f ) ret = max ( ret , c[f][pos] ) ; else ret += c[f][pos] ; pos += lowbit ( pos ) ; } return ret ; } int main () { int n , i , j , k ; while ( scanf ( "%d" , &n ) != EOF ) { int t = 0 ; memset ( c , 0 , sizeof ( c ) ) ; for ( i = 1 ; i <= n ; i ++ ) { scanf ( "%d%d" , &e[i].l , &e[i].r) ; x[++t] = e[i].l ; x[++t] = e[i].r ; } sort ( x + 1 , x + t + 1 ) ; t = unique ( x + 1 , x + t + 1 ) - x - 1 ; for ( i = 1 ; i <= n ; i ++ ) { e[i].l = lower_bound ( x + 1 , x + t + 1 , e[i].l ) - x ; e[i].r = lower_bound ( x + 1 , x + t + 1 , e[i].r ) - x ; } sort ( e + 1 , e + n + 1 ) ; int ans = -111111111 ; for ( i = 1 ; i <= n ; i ++ ) { int a = query ( 0 , e[i].l + 1 ) ; int b = query ( 1 , e[i].l + 1 ) ; // printf ( "a = %d , b = %d\n" , a , b ) ; ans = max ( ans , a - b - b ) ; update ( 1 , e[i].l , a ) ; update ( 0 , e[i].l , 1 ) ; } printf ( "%d\n" , ans ) ; } }