二分题 D - Salary Changing codeforce

题意：给出n个人（n是奇数），s钱；s为总的可以付工钱的钱；

每一个工人有一个付工钱的区间，只要在这个区间范围内，随便一个数都可以当作给这个工人付了钱；

老板要付给每个工人钱，并且付钱的中位数要尽可能大；

问：最大的中位数是多少；

思路：贪心+思维+二分；

我们以中位数为主体进行二分。那么就需要n/2+1个大于等于中位数的数；

这个时候我们先给钱排序，按第一个数从大到小排；

然后check部分，从1到n遍历，如果满足x在区间范围内，就取x这个数；

那么，为什么就要取这个数呢，因为我们迟早要凑到n/2+1个数，所以从大到小的排序，可以让我们在使用的钱

最少的情况下，取出这n/2+1个这样的数；比如有这样两个区间“6 10” ”7 11“ 按从大到小排序，我们假如中位数为8；

我们假如“6 10" 取中位数8 ”7 11“ 取左端点7 那么结果为15

如果”7 11“ 取中位数，另一个取左端点，则结果为14；

所以代码如下

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=2e5+;

 struct node

 {

     int l,r;

 }a[maxn];

 ll n;ll s;

 bool cmp(node x,node y)

 {

     return x.l>y.l;

 }

 int check(ll x)

 {

     ll sum=;

     ll num=n/+;

     for(int i=;i<=n;i++){

         //当num==0之后，所需要的大于等于n/2+1已经满足，所以都取

         //左端点即可；

         if(x>=a[i].l&&x<=a[i].r&&num>){

             sum+=x;

             num--;

         }

         else{

             sum+=a[i].l;

             if(a[i].l>=x) num--;

         }

     }

     if(num>) return ;

     else{

         if(sum>s) return ;

         else return ;

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--){

         scanf("%lld%lld",&n,&s);

         for(int i=;i<=n;i++){

             scanf("%d%d",&a[i].l,&a[i].r);

         }

         sort(a+,a++n,cmp);

         ll l=a[n/+].l;ll r=s;

         ll ans=l;

         while(l<=r){

             ll mid=l+r>>;

             if(check(mid)){

                 ans=mid;

                 l=mid+;

             }

             else r=mid-;

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

二分题 D - Salary Changing codeforce

最新文章

热门文章