Codeforces 1251D Salary Changing

D. Salary Changing

大意: 有n个变量, 每个变量有一个取值区间, 要求给这n个变量赋值, 使得n个变量的和不超过S且中位数尽量大(n一定为奇数)

二分答案, 中位数大于等于mid就是问能不能有(n+1)/2个变量的值大于等于mid, 排序贪心就完事了.

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long i64;

const int maxn = 200002;

struct interval{

    int l, r;

    bool operator < (const interval &B)const{

        return l < B.l;

    }

}E[maxn];

bool ok(int target, int n, i64 S){

    i64 cost = 0;

    int cnt = 0;

    for(int i=n;i>=1;--i){

        if(cnt*2<n&&E[i].r>=target){

            if(E[i].l>=target)cost += E[i].l;

            else cost += target;

            cnt++;

        }else{

            cost += E[i].l;

        }

    }

    return cost<=S && cnt*2>n;

}

void work(){

    i64 S;

    int n;

    scanf("%d%lld", &n, &S);

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

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

    }

    sort(E+1, E+n+1);

    int L = E[n/2+1].l;

    int R = 1000000000;

    while(L<=R){

        int mid = (L+R)>>1;

        if(ok(mid, n, S))L = mid + 1;

        else R = mid - 1;

    }

    printf("%d\n", L-1);

}

int main(){

    int t;scanf("%d", &t);

    while(t--){

        work();

    }

    return 0;

}

巴特西

Codeforces 1251D Salary Changing

最新文章

热门文章