本文主要是介绍Codeforces 1469 F. Power Sockets —— 二分+线段树，贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way
题意：
现在有一个根节点，和n条包含a[i]个节点的链。一开始所有点的颜色是白色的。你每次可以做以下操作：
找到树中某个白色节点，拿出一条链，将这个节点和链上某个节点连接，并且这两个点的颜色变成黑色，之后这条链属于树中一个部分。
你可以合并任意的链，问你离根节点第k远的白色点的深度最小是多少。
题解：
首先知道了一点：加入一条链的时候，两个白点会变成黑色，那么长度小于等于2的必不用加入。
并且长的链在前面一定是更优的，因为短链在前，再加长链的话，会使得更多的白点深度增加。
链接树上的白点时，一定是找深度最小的，连接链的时候，一定是链最中间的点。就像刚才说的一样，如果不是深度最小的话，更多的白点深度会增加。连接中间点的话，链上会有一半的点的深度降低。
但是我们不能白点数量一到k的时候就结束操作，因为可能能够在一些深度较低的白点上加链使得第k远的白点的深度减小。
于是这种最大值最小的题目我们一眼就知道是二分。
那么怎么知道当前第k远的点的深度，怎么知道深度最低的点的位置呢，使用线段树维护即可。
#include<bits/stdc++.h>
using namespace std;
const int N=8e5+5;
#define ll long long
ll sum[N*4],f[N*4];
void push_down(int l,int r,int root){if(!f[root])return ;int mid=l+r>>1;sum[root<<1]+=(mid-l+1)*f[root];sum[root<<1|1]+=(r-mid)*f[root];f[root<<1]+=f[root];f[root<<1|1]+=f[root];f[root]=0;
}
void update(int l,int r,int root,int ql,int qr,int v){if(l>=ql&&r<=qr){sum[root]+=(r-l+1)*v;f[root]+=v;return ;}int mid=l+r>>1;push_down(l,r,root);if(mid>=ql)update(l,mid,root<<1,ql,qr,v);if(mid<qr)update(mid+1,r,root<<1|1,ql,qr,v);sum[root]=sum[root<<1]+sum[root<<1|1];
}
int q_k(int l,int r,int root,int k){if(l==r)return l;int mid=l+r>>1;push_down(l,r,root);if(sum[root<<1]>=k)return q_k(l,mid,root<<1,k);else return q_k(mid+1,r,root<<1|1,k-sum[root<<1]);
}
int q_f(int l,int r,int root){if(l==r)return l;int mid=l+r>>1;push_down(l,r,root);if(sum[root<<1])return q_f(l,mid,root<<1);else return q_f(mid+1,r,root<<1|1);
}
int a[N],n,k;
bool cmp(int x,int y){return x>y;}
int check(int x){memset(sum,0,sizeof(sum)),memset(f,0,sizeof(f));update(1,N-1,1,2,1+(a[1]-1)/2,2);if(a[1]%2==0)update(1,N-1,1,1+a[1]/2,1+a[1]/2,1);for(int i=2;i<=n;i++){if(sum[1]>=k)if(q_k(1,N-1,1,k)<=x)return 1;if(a[i]<=2)return 0;int p=q_f(1,N-1,1);update(1,N-1,1,p,p,-1);update(1,N-1,1,p+2,min(N-1,p+1+(a[i]-1)/2),2);if(a[i]%2==0&&p+1+a[i]/2<=N-1)update(1,N-1,1,p+1+a[i]/2,p+1+a[i]/2,1);}if(sum[1]>=k)if(q_k(1,N-1,1,k)<=x)return 1;return 0;
}
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n,cmp);if(a[1]==2)return 0*printf("-1\n");int l=1,r=N-1,mid,ans=-1;while(r>=l){mid=l+r>>1;if(check(mid))r=mid-1,ans=mid;else l=mid+1;}printf("%d\n",ans?ans:-1);return 0;
}这篇关于Codeforces 1469 F. Power Sockets —— 二分+线段树，贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
