51nod 1380 夹克老爷的逢三抽一

堆 脑洞题

题意 n个人围成一圈

然后每次可以选一个人，得到他的分数，然后他与他相邻的两个人出圈

总共选 n/3次， 保证n是3的倍数

题解

这道怎么说呢，应该比较巧妙吧，你开一个优先队列，大根堆，每次选择优先队列中

最大的数，然后把他左右两个数删掉，

比如 A B C 删掉 B ，那么就把 A+C-B 加入优先队列中，

这其实就是相当于提供了一个后悔的机会，就像网络流中的反向边，

如果在选中这个点的话，就相当于 B+(A+C-B) 然后就相当于 B 这个点 不选 选A C两点

这不恰好是我们想要的吗。如果选了这个数不是最优解，我们可以有一个反悔的机会。

而且选的次数也不会错， 这样时间复杂度就是 O(N log N)

 

1 #include 
     
       2 #define ll long long  3 using namespace std ;  4  5 const int N = 1e5+11 ;  6 int n,x,num ;  7 ll a[N] ;  8 int l[N],r[N] ; 9 bool vis[N] ;  10 ll ans ; 11 struct node{12     ll val ; 13     int id ; 14 };15 struct cmp{16     bool operator() (node a,node b) 17     {18         return a.val < b.val ;     19     } 20 };21 node p ; 22 priority_queue 
      
       
        ,cmp> Q ; 23 24 inline ll read() 25 {26     ll x = 0 , f = 1 ;  27     char ch = getchar() ; 28     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 29     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 30     return x * f ; 31 }32 33 int main() 34 {35     n = read() ; 36     for(int i=1;i<=n;i++) 37     {38         a[ i ] = read() , l[ i ] = i-1 ,r[ i ] = i+1 ; 39         p.id = i ; p.val = a[ i ] ; 40         Q.push( p ) ; 41     }    42     l[ 1 ] = n ; r[ n ] = 1 ; 43     while(!Q.empty()) 44     {45         p = Q.top() ; 46         Q.pop() ; 47         x = p.id ; 48         if(vis[x]) continue ; 49         50         ans+=p.val ;       51         num++ ; 52         vis[ l[x] ] = 1 ; 53         vis[ r[x] ] = 1 ; 54         p.id = x ; a[ x ] = a[ l[x] ] + a[ r[x] ] -a[x] ;  55         p.val = a[ x ] ; 56         Q.push(p) ; 57         int L = l[l[x]] , R = r[r[x]] ; 58         l[x] = L ;  r[x] = R ;  59         r[L] = x ;  l[R] = x ; 60         if(num*3==n) break ; 61     }62     printf("%lld",ans) ; 63     return 0 ; 64 }