Codeforces1469F.PowerSockets——二分+线段树，贪心

This way

题意&＃xff1a;

现在有一个根节点&＃xff0c;和n条包含a[i]个节点的链。一开始所有点的颜色是白色的。你每次可以做以下操作&＃xff1a;
找到树中某个白色节点&＃xff0c;拿出一条链&＃xff0c;将这个节点和链上某个节点连接&＃xff0c;并且这两个点的颜色变成黑色&＃xff0c;之后这条链属于树中一个部分。
你可以合并任意的链&＃xff0c;问你离根节点第k远的白色点的深度最小是多少。

题解&＃xff1a;

首先知道了一点&＃xff1a;加入一条链的时候&＃xff0c;两个白点会变成黑色&＃xff0c;那么长度小于等于2的必不用加入。
并且长的链在前面一定是更优的&＃xff0c;因为短链在前&＃xff0c;再加长链的话&＃xff0c;会使得更多的白点深度增加。
链接树上的白点时&＃xff0c;一定是找深度最小的&＃xff0c;连接链的时候&＃xff0c;一定是链最中间的点。就像刚才说的一样&＃xff0c;如果不是深度最小的话&＃xff0c;更多的白点深度会增加。连接中间点的话&＃xff0c;链上会有一半的点的深度降低。
但是我们不能白点数量一到k的时候就结束操作&＃xff0c;因为可能能够在一些深度较低的白点上加链使得第k远的白点的深度减小。
于是这种最大值最小的题目我们一眼就知道是二分。
那么怎么知道当前第k远的点的深度&＃xff0c;怎么知道深度最低的点的位置呢&＃xff0c;使用线段树维护即可。

#include
using namespace std;
const int N&＃61;8e5&＃43;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&＃61;l&＃43;r>>1;sum[root<<1]&＃43;&＃61;(mid-l&＃43;1)*f[root];sum[root<<1|1]&＃43;&＃61;(r-mid)*f[root];f[root<<1]&＃43;&＃61;f[root];f[root<<1|1]&＃43;&＃61;f[root];f[root]&＃61;0;
}
void update(int l,int r,int root,int ql,int qr,int v){if(l>&＃61;ql&&r<&＃61;qr){sum[root]&＃43;&＃61;(r-l&＃43;1)*v;f[root]&＃43;&＃61;v;return ;}int mid&＃61;l&＃43;r>>1;push_down(l,r,root);if(mid>&＃61;ql)update(l,mid,root<<1,ql,qr,v);if(mid<qr)update(mid&＃43;1,r,root<<1|1,ql,qr,v);sum[root]&＃61;sum[root<<1]&＃43;sum[root<<1|1];
}
int q_k(int l,int r,int root,int k){if(l&＃61;&＃61;r)return l;int mid&＃61;l&＃43;r>>1;push_down(l,r,root);if(sum[root<<1]>&＃61;k)return q_k(l,mid,root<<1,k);else return q_k(mid&＃43;1,r,root<<1|1,k-sum[root<<1]);
}
int q_f(int l,int r,int root){if(l&＃61;&＃61;r)return l;int mid&＃61;l&＃43;r>>1;push_down(l,r,root);if(sum[root<<1])return q_f(l,mid,root<<1);else return q_f(mid&＃43;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&＃43;(a[1]-1)/2,2);if(a[1]%2&＃61;&＃61;0)update(1,N-1,1,1&＃43;a[1]/2,1&＃43;a[1]/2,1);for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;){if(sum[1]>&＃61;k)if(q_k(1,N-1,1,k)<&＃61;x)return 1;if(a[i]<&＃61;2)return 0;int p&＃61;q_f(1,N-1,1);update(1,N-1,1,p,p,-1);update(1,N-1,1,p&＃43;2,min(N-1,p&＃43;1&＃43;(a[i]-1)/2),2);if(a[i]%2&＃61;&＃61;0&&p&＃43;1&＃43;a[i]/2<&＃61;N-1)update(1,N-1,1,p&＃43;1&＃43;a[i]/2,p&＃43;1&＃43;a[i]/2,1);}if(sum[1]>&＃61;k)if(q_k(1,N-1,1,k)<&＃61;x)return 1;return 0;
}
int main()
{scanf("%d%d",&n,&k);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&a[i]);sort(a&＃43;1,a&＃43;1&＃43;n,cmp);if(a[1]&＃61;&＃61;2)return 0*printf("-1\n");int l&＃61;1,r&＃61;N-1,mid,ans&＃61;-1;while(r>&＃61;l){mid&＃61;l&＃43;r>>1;if(check(mid))r&＃61;mid-1,ans&＃61;mid;else l&＃61;mid&＃43;1;}printf("%d\n",ans?ans:-1);return 0;
}