题意分析
一共有s元钱，要用这些钱给n个人发工资，发给每个人的工资si有最少和最多限制 si ∈[li,ri]，在发给n个人的总工资小于s的情况下，要求发给n个人中的工资的中位数最大，并求出这个最大的中位数（数据满足：∑li <= s ）
解题思路
首先注意到发给n个人的工资的中位数mid和n个人所得总工资∑si 具有线性相关性，即 ∑si ∝ mid ，所以我们可以通过二分mid 求出求出满足条件的最优解
随后我们需要判断当前所得的中位数mid是否满足条件 ，显然，只要给至少n/2 + 1个人发的工资si >= mid ，并且∑si <= s ，则此mid满足条件
那么为了满足条件，我们会想着让更多的人发放的工资大于等于mid，同时∑si <= s，为此，我们这样设计判断函数check：
（1）预处理：因为每个人的工资至少有l[i] ，那么我们先为每个人分配最低工资l[i]，求得余下总工资 s = s - ∑l[i]
（2）预处理：将n个人的工资按最低工资升序排序
（3）使用的变量：
cnt：记录发放工资大于等于mid的总人数
sum：记录剩余的用于发放的钱
（4）处理方法：对于当前发放工资的中位数mid，从最低工资大的人开始向最低工资小的人枚举
1、若l[i] >= mid
显然，给这个人发放l[i]的工资即可，cnt++
2、若l[i] < mid <= r[i] && sum >= mid - l[i]
cnt++,sum -= mid - l[i]，表示将这个人的工资设置为mid，同时减去多给这个人的工资mid-l[i]
此时会有个疑惑，即为什么发给这个人的不是最低工资？这是一种贪心的思想，因为我们将n个人按最低工资升序排序，同时反向枚举n个人，这样保证了先枚举到的人的mid-l[i]更小，也就是说，我们用最少的代价使得更多的人的工资大于等于mid，这样一来，最后只需要判断cnt 是否大于等于 n/2 + 1 即可
代码区
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<string> #include<fstream> #include<vector> #include<stack> #include <map> #include <iomanip> #define bug cout << "**********" << endl #define show(x, y) cout<<"["<<x<<","<<y<<"] " #define LOCAL = 1; using namespace std; typedef long long ll; const ll inf = 1e18 + 7; const int Max = 4e5 + 10; struct Salary { int l,r; bool operator<(const Salary& s) const { return this->l < s.l; } }salary[Max]; int n; ll s; bool check(ll mid) { int cnt = 0; ll sum = s; for(int i = n ;i >= 1; i --) { if(salary[i].l >= mid) { cnt++; } else if(salary[i].r >= mid && sum >= mid - salary[i].l) // 为了让更多的人的工资大于mid，因此从最低工资大的人开始向前枚举，这样造成的额外工资最小， // 即总发放的工资最小 { cnt++; sum -= mid - salary[i].l; } } return cnt >= n/2 + 1; } int main() { #ifdef LOCAL // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int t; scanf("%d",&t); while(t--) { scanf("%d%lld",&n,&s); for(int i = 1;i<= n ;i ++) { scanf("%d%d",&salary[i].l,&salary[i].r); s -= salary[i].l; //保证必定取下界 } sort(salary+1,salary+1+n); ll l = salary[n/2+1].l,r = inf; while(l <= r) { ll mid = (l + r)>>1; if(check(mid)) l = mid +1; else r = mid -1; } printf("%lld\n",r); } return 0; }