题解 CF1251D 【Salary Changing】

Weakest_Konjac · 2020-01-12 20:14:37 · 题解

时间复杂度：O\left(Tn \ log \ n+Tn \ log \ s\right)

前置知识：二分答案+贪心

读完题目，不难想到二分答案。大概思路：二分中位数，贪心判断。问题主要是如何贪心判断是否满足。

我们把第i个员工的薪水范围表示为num\left[i\right].l,num\left[i\right].r，把当前中位数表示为mid。我们可以把员工的薪水分为三类：

第一类：薪水上界小于中位数，即num\left[i\right].r<mid

第二类：薪水下界大于中位数，即num\left[i\right].l>mid

第三类：薪水下界小于等于中位数，上界大于等于中位数，即num\left[i\right].l<=mid且num\left[i\right].r>=mid

对于第一类，薪水一定小于中位数，为了节省钱，我们支付num\left[i\right].l的薪水

对于第一类，薪水一定大于中位数，为了节省钱，我们支付num\left[i\right].l的薪水

然后我们通过第三类来调节大于等于中位数的薪水数和小于中位数的薪水数，让大于等于中位数的薪水数>小于中位数的薪水数

于是，对于第三类，我们还需支付薪水小于中位数的数量和支付薪水大于中位数的数量是确定的，所以为了节省钱，我们对于下界小的一部分，支付下界num\left[i\right].l，对于其他部分，支付中位数mid。

具体解释可看代码

代码如下：

#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
const int N=2e5+5;
struct node{
    int l,r;
}num[N];
struct cmp{
    inline bool operator () (const node&a,const node&b){
        return a.l<b.l;
    }
};
int T,n,tot[N];
long long s;
inline int check(long long mid){
    int cnt=0,cnt1=0,cnt2=0;//cnt为第三类薪水数，cnt1为第一类薪水数，cnt2位第二类薪水数
    long long sum=0;
    for (register int i=1;i<=n;++i)
        if (num[i].r<mid) sum+=num[i].l,++cnt1;//第一类
        else if (num[i].l>mid) sum+=num[i].l,++cnt2;//第二类
        else tot[++cnt]=i;//第三类薪水编号记录
    if (cnt1>(n>>1)||cnt2>(n>>1)) return 0;//如果第一类或第二类薪水数大于所有薪水数的一半，即大于或小于中位数的数大于一半，肯定不满足
    for (register int i=1;i<=(n>>1)-cnt1;++i) sum+=num[tot[i]].l;//对于num[i].l小的部分
    sum+=1ll*mid*((n>>1)+1-cnt2);//其他部分
    return sum<=s;
}
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d%lld",&n,&s);
        for (register int i=1;i<=n;++i) scanf("%d%d",&num[i].l,&num[i].r);
        sort(num+1,num+n+1,cmp());//将num[i].l从小到大排序
        long long l=num[(n>>1)+1].l,r=1ll*s/((n>>1)+1);//二分上下界自己极端估计一下
        while (l<=r){
            long long mid=l+r>>1;
            check(mid)?l=mid+1:r=mid-1;
        }
        printf("%lld\n",l-1);
    }
    return 0;
}