链接：

https://codeforces.com/contest/1251/problem/D

题意：

You are the head of a large enterprise. n people work at you, and n is odd (i. e. n is not divisible by 2).

You have to distribute salaries to your employees. Initially, you have s dollars for it, and the i-th employee should get a salary from li to ri dollars. You have to distribute salaries in such a way that the median salary is maximum possible.

To find the median of a sequence of odd length, you have to sort it and take the element in the middle position after sorting. For example:

the median of the sequence [5,1,10,17,6] is 6,

the median of the sequence [1,2,1] is 1.

It is guaranteed that you have enough money to pay the minimum salary, i.e l1+l2+⋯+ln≤s.

Note that you don't have to spend all your s dollars on salaries.

You have to answer t test cases.

思路：

二分，判断赛的时候贪心判断。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 2e5+10;

struct Node

{

    int l, r;

    bool operator < (const Node& rhs) const

    {

        if (this->l != rhs.l)

            return this->l > rhs.l;

        return this->r > rhs.r;

    }

}node[MAXN];

int n;

LL s;

bool Check(LL val)

{

    int p = n/2+1;

    LL sum = 0;

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

    {

        if (node[i].r >= val && p > 0)

        {

            sum += max(val, (LL)node[i].l);

            p--;

        }

        else

        {

            sum += node[i].l;

        }

    }

    return (sum <= s && p == 0);

}

int main()

{

    ios::sync_with_stdio(false);

    int t;

    cin >> t;

    while(t--)

    {

        cin >> n >> s;

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

            cin >> node[i].l >> node[i].r;

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

        LL l = 1, r = s;

        LL res = 0;

        while(l <= r)

        {

            LL mid = (l+r)/2;

            //cout << mid << endl;

            if (Check(mid))

            {

                res = max(res, mid);

                l = mid+1;

            }

            else

                r = mid-1;

        }

        cout << res << endl;

    }

    return 0;

}

巴特西

Educational Codeforces Round 75 (Rated for Div. 2) D. Salary Changing

链接：

题意：

思路：

代码：

最新文章

热门文章