题意：有 n 个人，每个人的工资的有个区间
[
l
,
r
]
[l,r]
[l,r]，你手上总共有
s
s
s 金额。你给这 n 个人发工资，工资金额必须满足他们的区间要求。问要使得中位数最大，最少要发多少钱出去。
直接二分答案，对当前答案求出最少需要的金额
f
f
f，对于
m
i
d
mid
mid， 至少要有
⌊
n
+
1
2
⌋
\lfloor\frac{n + 1}{2}\rfloor
⌊2n+1⌋ 个人的工资
≥
m
i
d
\geq mid
≥mid。将 n 个人划分成三类： 1.
r
<
m
i
d
r <mid
r<mid， 这类人发
l
l
l 的工资 2.
l
≤
m
i
d
≤
r
l \leq mid \leq r
l≤mid≤r，这类人按
l
l
l 排序，若工资
≥
m
i
d
\geq mid
≥mid 的人不够
⌊
n
+
1
2
⌋
\lfloor\frac{n + 1}{2}\rfloor
⌊2n+1⌋，则发
m
i
d
mid
mid，否则发
l
l
l 3.
m
i
d
<
l
mid < l
mid<l，这类人发
l
l
l ，由于
l
>
m
i
d
l > mid
l>mid，因先发这一类人
综上，将每个人的工资按
l
l
l 从大到小排序，二分答案，贪心构造即可。
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 2e5 + 10;
typedef long long ll
;
int t
;
ll L
[maxn
],R
[maxn
],n
,s
;
struct node
{
ll l
,r
;
node(ll li
= 0,ll ri
= 0) {
l
= li
;
r
= ri
;
}
bool operator < (const node
& rhs
) const {
if(l
== rhs
.l
) return r
> rhs
.r
;
return l
> rhs
.l
;
}
}a
[maxn
];
int main() {
scanf("%d",&t
);
while(t
--) {
scanf("%lld%lld",&n
,&s
);
for(int i
= 1; i
<= n
; i
++) {
scanf("%lld%lld",&a
[i
].l
,&a
[i
].r
);
}
sort(a
+ 1,a
+ n
+ 1);
ll l
= 0,r
= s
+ 1;
while(l
< r
) {
ll mid
= l
+ r
>> 1;
ll tmp
= 0,cnt
= 0;
for(int i
= 1; i
<= n
; i
++) {
if(mid
< a
[i
].l
){
tmp
+= a
[i
].l
;
cnt
++;
} else if(a
[i
].l
<= mid
&& mid
<= a
[i
].r
) {
if(cnt
< (n
+ 1) / 2) tmp
+= mid
,cnt
++;
else tmp
+= a
[i
].l
;
} else if(a
[i
].r
< mid
) tmp
+= a
[i
].l
;
}
if(cnt
>= (n
+ 1) / 2 && tmp
<= s
) l
= mid
+ 1;
else r
= mid
;
}
printf("%lld\n",l
- 1);
}
return 0;
}
