题意
https://vjudge.net/problem/CodeForces-1251D
您是一个大型企业的负责人。在您的企业当中共有n位员工为您工作，而且非常有趣的事是这个n是一个奇数（n不能被2整除）。
您必须给你的员工分配工资。最初，您有s美元，而第ii个员工应得的薪水应该是li∼ri之间的一个值。而无论怎么分配每个人的工资，您必须使得所有分配的工资的中位数最大。
对于一个长度为奇数的序列，如果要找到他的中位数，就需要先对这个序列进行排序，之后找到中间位置的数字。举例来说：
- 序列[5,1,10,17,6]的中位数是6
- 序列[1,2,1]的中位数是1
保证您有足够的钱来支付最低的工资，即l1+l2+⋯+ln≤s。
注意，您不必把所有的钱都花在员工的开支上。
思路
假设符合要求的中位数为x，首先，按右端点从小到大排序，ri的中位数即是x的上界；按左端点排序，得到x的下界为li的中位数。这个很好理解，画个数轴，基本就是那回事。。然后我们在x的上下界里二分，check所花费用是否小于等于s即可。怎么check呢？考虑贪心，对于ri<x的数，我们就取li，这样可以腾出更多的资金；对于li>x的数，我们取li，也是为了腾出更多资金；对于li~ri穿插x的数，我们先丢一起。通过刚才的判断我们可以得到放到x左边和右边的个数，现在我们遍历穿插的数，如果当前x左边的个数小于右边，那么这个数得用来放到左边，用最小的li即可；否则放到右边，用x的值即可。最后还剩一个数，那就是中位数x啦，所以判断tmp+x<=s即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
struct node
{
ll l,r;
} g[N];
int n;
ll s;
bool cmp1(node a,node b)
{
return a.l<b.l;
}
bool cmp2(node a,node b)
{
return a.r<b.r;
}
node gg[N];
bool check(ll x)
{
ll tmp=0,l=0,r=0,cnt=0;
for(int i=1; i<=n; i++)
{
if(g[i].l>x)
tmp+=g[i].l,r++;
else if(g[i].r<x)
{
tmp+=g[i].l,l++;
}
else
{
gg[cnt++]=g[i];
}
}
int i=0,j=cnt-1;
while(i<j)
{
if(l<r)
tmp+=gg[i].l,l++,i++;
else
tmp+=x,r++,j--;
}
// cout<<"gg"<<endl;
return tmp+x<=s;
}
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
cin>>n>>s;
for(int i=1; i<=n; i++)
{
cin>>g[i].l>>g[i].r;
}
sort(g+1,g+1+n,cmp2);
ll R=g[n/2+1].r;
sort(g+1,g+1+n,cmp1);
ll L=g[n/2+1].l;
ll l=L,r=R,mid,ans=L;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else
r=mid-1;
}
cout<<ans<<endl;
}
return 0;
}