題意
https://vjudge.net/problem/CodeForces-1251D
您是一個大型企業的負責人，在您的企業當中共有n位員工為您作業，而且非常有趣的事是這個n是一個奇數（n不能被2整除），
您必須給你的員工分配工資，最初，您有s美元，而第ii個員工應得的薪水應該是li?～ri?之間的一個值，而無論怎么分配每個人的工資，您必須使得所有分配的工資的中位數最大，
對于一個長度為奇數的序列，如果要找到他的中位數，就需要先對這個序列進行排序，之后找到中間位置的數字，舉例來說：
- 序列[5,1,10,17,6]的中位數是6
- 序列[1,2,1]的中位數是1
保證您有足夠的錢來支付最低的工資，即l1?+l2?+?+ln?≤s，
注意，您不必把所有的錢都花在員工的開支上，
思路
假設符合要求的中位數為x，首先，按右端點從小到大排序，ri的中位數即是x的上界；按左端點排序，得到x的下界為li的中位數，這個很好理解，畫個數軸，基本就是那回事，，然后我們在x的上下界里二分，check所花費用是否小于等于s即可，怎么check呢？考慮貪心，對于ri<x的數，我們就取li，這樣可以騰出更多的資金；對于li>x的數，我們取li，也是為了騰出更多資金；對于li~ri穿插x的數，我們先丟一起，通過剛才的判斷我們可以得到放到x左邊和右邊的個數，現在我們遍歷穿插的數，如果當前x左邊的個數小于右邊，那么這個數得用來放到左邊，用最小的li即可；否則放到右邊，用x的值即可，最后還剩一個數，那就是中位數x啦，所以判斷tmp+x<=s即可，
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
struct node
{
ll l,r;
} g[N];
int n;
ll s;
bool cmp1(node a,node b)
{
return a.l<b.l;
}
bool cmp2(node a,node b)
{
return a.r<b.r;
}
node gg[N];
bool check(ll x)
{
ll tmp=0,l=0,r=0,cnt=0;
for(int i=1; i<=n; i++)
{
if(g[i].l>x)
tmp+=g[i].l,r++;
else if(g[i].r<x)
{
tmp+=g[i].l,l++;
}
else
{
gg[cnt++]=g[i];
}
}
int i=0,j=cnt-1;
while(i<j)
{
if(l<r)
tmp+=gg[i].l,l++,i++;
else
tmp+=x,r++,j--;
}
// cout<<"gg"<<endl;
return tmp+x<=s;
}
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
cin>>n>>s;
for(int i=1; i<=n; i++)
{
cin>>g[i].l>>g[i].r;
}
sort(g+1,g+1+n,cmp2);
ll R=g[n/2+1].r;
sort(g+1,g+1+n,cmp1);
ll L=g[n/2+1].l;
ll l=L,r=R,mid,ans=L;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else
r=mid-1;
}
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/124306.html
標籤：其他
上一篇：Kickstart Round H 2019 Problem B. Diagonal Puzzle
下一篇：圖-普利姆演算法